\(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]\)。
操作都是在 \(Trie\) 树上进行。
这是可以通过 \(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;
for(int i=1;i<len2;i++){
int x=fail[i];
while(x&&s[x]!=s[i])x=fail[x];
fail[i+1]=(s[x]==s[i]?x+1:0);
}