Aho-Corasick 算法

Aho-Corasick 算法在 1975 年产生于贝尔实验室，是著名的多模匹配算法之一。一个常见的例子就是给出 n 个单词，再给出一段包含 m 个字符的文章，让你找出有多少个单词在文章里出现过。KMP 中我们用两个指针 i 和 j 分别表示，A[i-j+ 1..i] 与 B[1..j] 完全相等。也就是说，i 是不断增加的，随着 i 的增加 j 相应地变化，且 j 满足以 A[i] 结尾的长度为 j 的字符串正好匹配 B 串的前 j 个字符，当 A[i+1]≠B[j+1]，KMP 的策略是调整 j 的位置(减小 j 值)使得 A[i-j+1..i] 与 B[1..j] 保持匹配且新的 B[j+1] 恰好与 A[i+1] 匹配，而 next 函数恰恰记录了这个 j 应该调整到的位置。同样 AC 自动机的失败指针具有同样的功能，自动机本身是计算理论的一个概念；其实是一张“图”，每个点是一个“状态”，而边则是状态之间的转移，根据条件能指导从一个状态走向另一个状态。很多字符串匹配算法都是基于自动机模型的，比如被广泛使用的正则表达式。AC 自动机算法算是比较简单直观的字符串匹配自动机，它其实就是在一颗 Trie 树上建一些失配指针，当失配时只要顺着失配指针走，就能避免一些重复的计算。比如对于字符串 antibody 和 tide，如果第一个串匹配到第 5 个字符(b)失配了可以直接走入第二个串的第 3 个字符(d)进行匹配，因为前面的“ti”是公共的，如果能匹配到第一个串的第 5 个字符，那么前面两个肯定是 ti。