$AC$ 自动机 $=TRIE+KMP$
所有的模式串构成一棵 $TRIE$ 。并在 $Trie$ 树上所有结点构造失配指针： $KMP$ 思想。
为了进行多模式匹配。
$Trie$ 构建操作和 $trie$ 的 $insert$ 的操作一模一样，其中每个结点代表某个字符串（也有可能是很多个）的某个前缀。
构建 $fail$ 指针：
和 $KMP$ 一样，是失配的时候用于跳转的指针。
$KMP$ 要求最长相同真前后缀，但是 $AC$ 自动机只需要相同后缀。即状态 $u$ 的 $fail$ 指针指向另一个状态 $v$ ， $v$ 是 $u$ 的最长后缀，有可能来自不同的字符串。
现在假设字典树中有一个结点 $u$ ， $u$ 的父节点是 $p$ ， $p$ 通过字符 $c$ 的边指向 $u$ 。即 $ch[p] [c]=u$ 。现在分情况讨论：
如果 $ch[fail[p]] [c]$ 存在，那么相当于失配那个状态后面也恰好有字符 $c$ 。所以现在这个状态往下延伸字符 $c$ ，刚好失配那里也可以匹配到，于是 $u$ 的 $fail$ 指针指向 $ch[fail[p]] [c]$ 。
如果 $ch[fail[p]] [c]$ 不存在，说明这个失配的状态不满足，需要继续跳 $fail$ ，就是 $ch[fail[fail[p]]] [c]$ ，一直重复下去，直到 $fail$ 指针跳到根节点，此时没有办法，将 $fail$ 指针指向根节点。
建树函数 $build()$ ：目标是构建 $fail$ 指针以及构建自动机。我们采用 $BFS$ 来遍历字典树。
先给根节点自己连 $fail$ 指针，指向自己，接着对根节点连出去的边开始操作。
如果根节点连向某个字符，就把 $fail$ 指针指到根节点，毕竟长度为 $1$ ，失配就无了。然后把这个深度为 $1$ 的点入队。
接下来，当队列不为空时我们每次取队首，就是 $BFS$ 啦，并且取出的点在之前已经求过了 $fail$ 指针。之后这个点就相当于上文提到的 $p$ 。如果他连出了某一条边，那么他这个儿子的失配位置，就是他的失配位置向下连这个字符的边（这里按照上面所说应该分类讨论不存在一直跳 $fail$ ，但是我们做了一些操作简化），并且将这个儿子入队。如果不存在这个儿子，就连到失配位置的对应字符的边，这样前一种指向的边其实已经是一直跳 $fail$ 的结果了，相当于路径压缩。
匹配函数 $query()$ ：
循环遍历匹配串，用一个变量 $nownode$ 记录当前位置，利用 $fail$ 指针找出所有匹配的模式串，累加到答案中，然后清零。再来一个 $tmpnode$ 一直跳 $fail$ 指针，而不动 $nownode$ 。
时间复杂度：连了 $trie$ 图的复杂度是 $O(\sum |s_{i}|+n|\sum|+|S|)$ ， $n$ 是 $AC$ 自动机的结点数目，最大可以到 $O(\sum |s_{i}|)$ 。
如果这么写就裂开了。因为对于都是 $a$ 的字符串，跳 $fail$ 会一个一个跳，复杂度可能到平方级别。但注意到，我们每次都要跳 $fail$ ，于是我们只需要把 $fail$ 指针指向的点作为该节点的父亲，然后树形 $dp$ 一下，就好了。
给定 $n$ 个字符串和一个长度 $k$ ，让求一个字符串长度为此长度，且这些字符串在这个字符串中出现次数之和最大。 $n≤20,k≤10^{3},$，这些字符串长度均不超过 $15$ 。所有字符串只含有 $A,B,C$ 。
显然是个 $dp$ 。如果设 $dp[i][j]$表示长度到 $i$ ，后十五个字符为状态 $j$ （状压一下）的最大个数。这样复杂度是爆炸的，这些状态里有很多是不合适的，有很多是血亏的，其实我们只需要这些字符串中某些字符串的后缀往下走就好了，所以考虑 $AC$ 自动机。这样我们第二维其实就是所有字符串的状态节点数，这个节点数是不会超过 $300$ 的。
然后是 $dp$ 的转移， $dp[i][ch[j][k]]=max(dp[i][ch[j][k]],dp[i-1][j]+val[ch[j][k]])$ ，那么问题在于怎么计算 $val$ 数组。这个数组代表我到了这个结点，有多少个字符串新出现了，首先，以这个点为结尾的字符串数要算上，之后，对于跳 $fail$ 结点，显然也可以算到这个里面，所以有 $val[u]=val[fail[u]]+cnt[u]$ ，其中 $cnt[u]$ 是字符串们在这个点出现了多少次，这个插入的时候可以算。这里我们在 $BFS$ 的时候进行计算，这样失配点的答案已经是正确的，所以当前点的答案也是正确的。
给定一个长度不超过 $10^{5}$ 的字符串，又给了 $n$ 个单词记为 $t_{1},t_{2},……,t_{n}$ 。每次删除在大字符串中出现最早的列表中的单词，然后拼接，直到不能再删，保证列表中单词不会出现一个单词是另一个单词子串的情况，让输出最后的字符串。
建立 $AC$ 自动机，遇到某个字符串的结尾，就删掉，用一个栈存有哪些字符还留着，删的时候一直弹栈，然后跳到栈顶代表的结点就行了，最后输出栈中所有字符即可。