\(\text{Pt.} 1\) 基础
一、进制哈希
二、Manacher
三、Trie
\(\text{Pt.} 2\) 自动机
自动机是什么？它是一个对“信息序列”进行判定的数学模型。“信息序列”可以很随意，比如一个二进制数，比如一个字符串。而“判定”也可以很随意，比如判定一个二进制数是不是奇数，判定当前字符串是不是某个字符串的子串。
它的本质是一个有向图。它里面的节点分为两种：“接受节点”和“不接受节点”，在哪个地方停下就说明是判定成功还是不成功。
具体的一个判定过程是这样的：从一个代表“空”的起始节点开始，逐步地往里面插入信息序列的每一个元素。直到插完了或是走不动了，就停下来，进行判定。
是不是很像 Trie？没错，Trie 就是一种自动机。下面的算法都是自动机。（不知道能不能这么说，因为 OIwiki 上说自动机是一种数学模型，不能等同于 data stracture、algorithm 之流……）
自动机的基本套路：用于向末尾插入新节点时动态维护信息；有一个 Fail 指针，用于失配之后跳向之前的后缀，即“如果这个串不行，就试试它的后缀可不可以”的思想。