acam 小记

acam 作为多模匹配算法，很多东西与 kmp 相同，另外增添了 fail 树上操作的关键性质。

朴素 acam 就是 trie 树，fail 指针就是在当前 node 找一个后缀，使得在其他串存在一个前缀是这个后缀（类似 kmp）。

trie 图，就是简单优化了这个"树上乱跳"的过程，补全每个节点的儿子，类似于路径压缩。

其实 trie 图保证了走文本串时，一定可以找到一个对应节点（就是正常 u = tr[u][i]）。

一个关键部分是 acam 上 DP。

也非常好理解，就是把 \(u\) 以及其他必要部分塞进状态里，用有效节点避免了状压。

另一个关键部分是 fail 树。执行以下指令

for (; u; u = fail[u]) {...}

放在 fail 树上就是不断跳祖先。于是可能可以用图论数据结构进行优化。