脚本宝典收集整理的这篇文章主要介绍了常见字符串算法 II：自动机相关，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
建议先学习 确定有限状态自动机。
基本定义与约定：
前置知识：Trie 树与 KMP 算法。
AC 自动机是一类 DFA，全称为 Aho-Corasick Automaton，简称 ACAM。
AC 自动机用于解决多模式串匹配问题：形如给定字典 (s_i) 和文本串 (t)，求每个单词在 (t) 中出现的次数（当然，实际应用远超这一基本问题）。ACAM 与 KMP 的不同点在于后者仅有一个模式串，而前者有多个模式串。
朴素的用 KMP 实现的暴力时间复杂度为 (|t|times N + sum |s_i|)，其中 (N) 是单词个数。这是因为进行一次匹配的时间复杂度为 (|s_i| + |t|)。当单词数量 (N) 很大的时候显然无法接受。
多串匹配自然首先考虑建出字典树。根据定义，字典树上任意结点与所有 (s_i) 的某个前缀一一对应，设结点（也称状态）(i) 所表示的字符串为 (t_i)。借鉴 KMP 的思想，考虑对于每个状态 (qin Q) 其中 (Q) 是状态集合也即 trie 树上的所有结点，求出其失配指针 (fail_q)。这里失配指针的含义为 (q) 所表示字符串 (t_q) 的最长真后缀 (t_q[j,|t_q|] (2leq jleq |t_q|+1)) 使得该后缀作为某个 (s_i) 的前缀出现（这说明 (t_q[j,|t_q|]) 也对应了 trie 树上的一个状态），从 (q) 向字符串 (t_q[j,|t_q|]) 所对应的状态 (q’) 连一条有向边。
例如当 (s = {texttt{b}, texttt{ab}}) 时，(tt ab) 所表示状态会向 (tt b) 所表示状态连边，因为 (tt ab) 最长的（也是唯一的）在 (s_i) 中作为前缀出现的后缀为 (tt b)。再例如当 (s = {texttt{aba}, texttt {baba}}) 时，(tt ab) 会向 (tt b) 连边， (tt bab) 会向 (tt ab) 连边，(tt aba) 会向 (tt ba) 连边，而 (tt baba) 会向 (tt aba) 连边。对于每一条有向边 (qto q’)，后者是前者的后缀，也是 (s_i) 的一个前缀。
考虑用类似 KMP 的算法求得失配指针：令 (fail_qgets fail_{fa_q})。若当前的 (fail_q) 没有 (fa_qto q) 这条字典树上的边所表示的字符 (c) 的转移，则令 (fail_qgets fail_{fail_q})，否则 (fail_q) 即为 (mathrm{trans}(fail_q, c))，即字典树上在 (fail_q) 处添加字符 (c) 后到达的子状态，在代码中即 son[fail[q]][c]。
失配指针已经足够强大了，但这并不是 AC 自动机的完全体。既然叫自动机，那么对于每个状态的每个字符转移 (delta(i, c))，都应该封闭在状态集合 (Q) 里面。我们把 KMP 自动机的转移拎出来观察：
类似的，设字典树的根为结点 (0)，AC 自动机的转移可以写为：
其中 (delta(i,c)) 表示往状态 (i) 后添加字符 (c)，所得字符串的最长的与 (s_i) 前缀匹配的后缀所表示的状态，可以类比 KMP 的最长真前缀后缀理解。
性质：当 (mathrm{trans}(i, c)) 存在时，设其为 (q)， 则有 (fail_q = delta(fail_i, c))。这一点结合 (fail_i) 的最长性也好理解：向 (i) 添加字符 (c) 得到的状态的失配指针等于 (i) 的失配指针添加 (c) 得到的状态，因为若 (q) 的失配指针比 (delta(fail_i, c)) 更长，那么 (delta(fail_i, c)) 总可以变得和 (q) 的失配指针一样长，与 (delta) 的最大性矛盾。简单地说，就是必然有 (|delta(fail_i,c)|geq |fail_q|)，同时 (|fail_q|) 可以等于 (|delta(fail_i,c)|)，这里在一个状态 (q) 两侧加上绝对值符号表示其所对应字符串长度即 (|t_q|)。有了这一性质，我们就不需要预先求出失配指针，而是在建造 AC 自动机的同时一并求出。
由于我们需要保证在计算一个状态的转移时，其失配指针指向的状态的转移已经计算完毕，又因为失配指针长度必然小于原串长度（需要是真后缀），故使用 BFS 建立 AC 自动机。一般形式的 AC 自动机代码如下，非常好写：
int node, son[N][S], fa[N];
void ins(string s) { // 建出 trie 树
int p = 0;
for(char it : s) {
if(!son[p][it - 'a']) son[p][it - 'a'] = ++node;
p = son[p][it - 'a'];
}
}
void build() { // 建出 AC 自动机
queue <int> q;
for(int i = 0; i < S; i++) if(son[0][i]) q.push(son[0][i]); // 对于第一层特判一下，因为 fa[0] = 0，此处即转移的第二种情况
while(!q.empty()) { // 求得的 son[t][i] 就是文章中的转移函数 delta(t, i) 啦，相当于把 trie 的转移函数和 AC 自动机合并起来了
int t = q.front(); q.pop();
for(int i = 0; i < S; i++)
if(son[t][i]) fa[son[t][i]] = son[fa[t]][i], q.push(son[t][i]); // 转移的第一种情况：原 trie 图有 trans(t, i) 的转移
else son[t][i] = son[fa[t]][i]; // 转移的第三种情况
}
}
特别地，在 ACAM 上会有一些终止结点 (p) 表示一个单词或以一个单词结尾，即 (p) 对应的字符串 (t_p) 的某个后缀在字典 (s_i) 中出现。 若状态 (p) 本身表示一个单词，即 (t_pin {s_i})，则称为单词结点。所有终止结点 (p) 组成的集合对应着 DFA 中的接受状态集合 (F)：ACAM 接受且仅接受以给定词典中的某一个单词结尾的字符串。
总结一下我们使用到的约定：
fail 树有着非常好的性质：
性质 1：对于一个结点 (p) 及其对应字符串 (t_p)，其在 fail 树上的子树内部所有结点 (qin mathrm{subtree}(p))，都有 (t_p) 是 (t_q) 的后缀，且 (t_p) 是 (t_q) 的后缀当且仅当 (qin mathrm{subtree}(p))。根据失配指针的定义易证。
性质 2：若 (p) 是终止结点，则 (p) 的子树全部都是终止结点。
性质 3：定义 (ed_p) 表示 (t_p) 作为单词的后缀数量，则 (ed_p) 等于在 fail 树上从 (p) 到根结点上单词结点的权值之和，其中单词结点 (q) 的权值为与 (t_q) 相等的单词数量（可能出现重复单词，若单词互不相同显然单词结点权值为 (1)）。这一点也是由失配指针的定义得到。
根据性质 3，有这样一类问题：单词有带修权值，多次询问对于某个给定的字符串 (S)，所有单词的权值乘以其在 (S) 中出现次数之和。初步转化为 fail 树上修点权以及查询从根到某个结点的权值之和。
通常来说链上求和要用到树剖，但查询有特殊性质：一个端点是根。因此，我们使用 “相对论”：与其单点修改链上求和，不如子树修改单点查询。实时维护每个结点的答案，这样修改一个点相当于更新子树，而查询时只需要单点查询了。转化之前的问题需要树剖 + 数据结构 (log^2) 维护，但转化后即可 dfs 序 + 树状数组单 (log) 解决。
build 建出 AC 自动机！以上是脚本宝典为你收集整理的常见字符串算法 II：自动机相关全部内容，希望文章能够帮你解决常见字符串算法 II：自动机相关所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。