前言
最近新学了后缀自动机，回文自动机，感觉以前学的还是掌握的不深，于是总结一下字符串中的几个数据结构，进行一个复习，可能要写几天，待完成（对现在而言）。
AC自动机
Trie树
对于字符串来讲，这应该是最基础的数据结构。
\(Trie\) 树的每一条边代表一个字符，每个节点代表一个字符串，具体指从根节点到该节点经过的所有边的字符的合集，根节点编号为0。
例如上图中，从根节点到9号节点有 \(b\)，\(e\)，\(e\)，三条边，于是9号节点代表的字符串便是 \(bee\)。
每当我们向 \(Trie\) 树中加入一个字符串，我们将加入的初始位置设为根，每加入一个字符，寻找当前位置是否有连该字符的边，比如对于上图，我现在要加 \(beg\)，根节点已经向1号节点连边 \(b\)，我们就直接挪至3号节点，同理，我们可以继续移至8号节点，然后我们发现8号节点并未向下连一条 \(g\) 的边，因此我们建一个新节点，向它连边 \(g\)。
在判断这方面，我们用 \(go[i][j]\) 来储存 \(i\) 号节点是否练了字符 \(j\) 的边，存储的值就是连边的目标节点。
代码
void push(){
int t=0;
for(int i=0;i<len;i++){
int tt=c[i]-‘a‘;
if(!go[t][tt])go[t][tt]=++cnt;
t=go[t][tt];
}
isend[t]++;
}
KMP
对于字符串问题，我们通常需要去处理匹配问题，例如在字符串 \(A\) 中找字符串 \(B\)，我们可能找了很长一段之后，失配了，我们会迫不得已重新从开头寻找，将当次的起点向后挪一位，然后再从新的起点一个个匹配，但如果我们能找到在当前已匹配的 \(B\)的字串的一段后缀，使它恰好与相同长度的 \(B\) 的前缀相同，那是不是会很方便，我们可以继续在已枚举到的 \(A\) 的位置继续向下匹配，而不是回退很多，从头再来，例如下图。
绿色标出的便是前文所说的那一段后缀，相当于如果我们找到了这样一段，我们就可以仅仅将当前要所寻的 \(B\) 的位置更改，而对 \(A\) 仍照常找下去。
而对于这样一个后缀的寻找，我们就要用到 \(KMP\)。
我们用\(fail[i]\)表示对于 \(B\) 串的位置 \(i\)，以 \(i\) 为结尾的最长的满足等于对应长度前缀的后缀，即 \(c[1\) \(to\) \(fail[i]]\) \(=\) \(c[i-fail[i]+1\) \(to\) \(i]\)。
这是可以通过 \(fail[i-1]\) 求得的，如果 \(fail[i-1]\) 的后一个字符等于 \(c[i]\)，说明什么，相当于在 \(i-1\) 找到的 \(B\) 的前缀和相同的以 \(i-1\) 的结尾的后缀后面都有一个 \(c[i]\)。这样 \(fail[i]\)就等于 \(fail[i-1]+1\)，对吧？那如果没边呢，我们去考虑 \(fail[fail[i-1]]\)，这样也还是能执行上一操作，因为前 \(fail[i-1]\) 个字符的后缀，也相当于 \(c[i-1-fail[i-1]+1\) \(to\) \(i-1]\) 的后缀，所以 \(fail[i-1]\) 处理时找到的那个前缀，依旧满足是 \(i-1\) 的一个后缀，所以仍能继续执行该操作。
所以在代码中我们每次通过 \(fail[i]\) 去推 \(fail[i+1]\)，在前面的匹配问题中，我们发现 \(fail[i]\) 一定要小于 \(i\)，这样才能保证不会一直停留在同一个位置，\(c[1\) \(to\) \(i]\) \(=\) \(c[1\) \(to\) \(i]\) 是没有意义的，对吧，所以我们将 \(fail[1]\) 赋值为0。
代码
复杂度证明（包括构建与匹配）
构建：由于每个位置的 \(fail\) 是从上一个位置的 \(fail\) 开始往回跳，设不停向回跳至无法继续回跳所需要的次数为 \(k\)，那么构建时 \(k+=1\) 最多有 \(m\) 次，因为回跳时 \(k-=1\)，所以最多回跳 \(m\) 次。证毕。
匹配：最多向右走 \(n\) 次，而每次向左跳 \(fail\)一定会移动至少一个单位，所以最多向左跳 \(n\) 次。
Trie+KMP=AC/xk
如题，相当于 \(Trie\) 树上进行 \(KMP\) 匹配，也就是我们处理了一个带 \(fail\) 边的 \(Trie\) 树。
它通常用于处理一个字符串在多个字符串中寻找匹配。
对于 \(AC\)自动机，\(fail[i]\) 表示以 \(i\) 结点为结尾最长的匹配根缀的后缀，对应的根缀为 \(fail[i]\) 结点对应的字符串。注意 \(fail\) 的定义与 \(KMP\) 稍有区别（\(KMP\) 的 \(fail[i]\) 定义中为以 \(i-1\) 结尾的后缀）。
\(AC\)自动机上跳 \(fail\) 一定会跳到更短的字符串上，所以按 \(BFS\) 顺序推导 \(fail\) 值。
代码
插入与 \(Tire\) 树相同。
构建 \(fail\) 指针