Aho–Corasick 算法，AC 自动机
AHO 算法，或者叫 AC 自动机、又或者叫 Aho–Corasick string matching algorithm，是一个高效的多模式匹配算法，它的特点是可以同时匹配多个模式串。 最常见的应用就是病毒扫描 : 把所有病毒的特征码（类似一段字符串）构造成一个 AC 自动机，把用户的文件或者网络数据流作为输入文本，只要在输入文本中找到了任何一个特征码，那么就表示有病毒存在。 对于这样的一个应用场景，我们最希望的功能就是只扫描一遍输入文本，找出所有的病毒，而 AC 自动机恰恰就有这样的能力。 一般使用 AC 自动机需要以下三步： 根据待匹配的字符串 P1, P2, Pn 建立 Trie 给 Trie 添加失败路径，实际上是生成了一个自动机。 将输入文本 str 的字符逐个通过自动机，在 O(n) 的时间复杂度内找出 P1, P2 … Pn 是否存在于 str 内。 举例 假设我们有模式字符串 { fat, fare, hat, are }， 输入的文本为 “fatehatfare”。 显然，所有的模式串都出现在了我们的输入文本中。我们的目标就是只扫描一遍文本串，找出所有的模式串。 建立 Trie 首先根据模式串建立起一个 trie，一般来说每个节点的结构大概是这样： Node { Node * children[26]; /* 指向子节点的指针 */ Node * parent; /* 指向父节点的指针 */ Node * fail; /* 失败指针 */ bool terminate; /* 是否是一个终结节点，即一个串的最后一个字符 */ } Trie 建立好之后大概是这个样子： ...