备注：我不知道 fail 会不会和什么东西重名。（因为感觉这个单词挺完整的）
自动机的概念
不是很清楚自动机的概念。暂且认为：
自动机是一个有向图。点（状态）代表字符串（可能不止一个），边（转移）（可能）带一个字符，表示在字符串的末尾加上这个字符后到达的状态。有一个源点（PAM 有两个），代表初始状态。有若干个结束状态。从初始状态到结束状态的路径形成的字符串被自动机接受。
KMPAM、ACAM、PAM、SAM 都有一棵辅助的树，和自动机的图一起构建。有时需要在这棵树上解决问题。
- DFA（确定性有限状态自动机）：每条转移边都有字符，如“压缩路径”后的 ACAM。
- NFA（非确定性有限状态自动机）：有转移边没有字符，如没有“压缩路径”的 ACAM，fail 边就没有字符。
Trie（DFA）
Trie 居然也算自动机！
KMP 自动机（DFA）
就是把 KMP 中跳 fail 的结果预处理出来。（路径压缩）
ch[i][c]（当前站在第 \(i\) 位，要在后面加一个编号为 \(c\) 的字符）表示两种东西：
-
s[i + 1] == c，那么 ch[i][c] = i + 1
-
s[i + 1] != c，那么 ch[i][c] = ch[fail[i]][c] （？）（因为当 \(i \geq 1\) 时 fail[i] < i，所以从小到大枚举 \(i\)，用这个式子推即可）（前面路径压缩了，所以不用多次跳 fail）
AC 自动机（NFA）
在 Trie 上
标签：字符,ch,Trie,路径,fail,自动机,合集 From： https://www.cnblogs.com/huangkxQwQ/p/18360350