算法简介

在计算机科学中，Aho–Corasick算法是由Alfred V. Aho和Margaret J.Corasick 发明的字符串搜索算法，用于在输入的一串字符串中匹配有限组“字典”中的子串^ [1]^。它与普通字符串匹配的不同点在于同时与所有字典串进行匹配。算法均摊情况下具有近似于线性的时间复杂度，约为字符串的长度加所有匹配的数量。然而由于需要找到所有匹配数，如果每个子串互相匹配（如字典为a，aa，aaa，aaaa，输入的字符串为aaaa），算法的时间复杂度会近似于匹配的二次函数。

AC自动机算法主要依靠构造一个有限状态机（类似于在一个trie树中添加失配指针）来实现。这些额外的失配指针允许在查找字符串失败时进行回退（例如设Trie树的单词cat匹配失败，但是在Trie树中存在另一个单词cart，失配指针就会指向前缀ca），转向某前缀的其他分支，免于重复匹配前缀，提高算法效率。

代码实现

代码实现可以参考

步骤

1. 输入关键字集合构建前缀树

例如有三个关键字

Hello
world
haha

构建前缀树

先输入 Hello ，构建出

graph LR 0--H-->1--e-->2--l-->3--l-->4--O-->5;

接着输入 world，构建出

graph LR 0--H-->1--e-->2--l-->3--l-->4--O-->5; 0--w-->6--O-->7--r-->8--l-->9--d-->10;

接着输入 haha，构建出

graph LR 0--H-->1--e-->2--l-->3--l-->4--O-->5; 0--w-->6--O-->7--r-->8--l-->9--d-->10; 0--h-->11--a-->12--h-->13--a-->14;

2. 寻找每个节点的失效跳转节点

  1. 深度为 0 的节点（根节点），失败跳转节点是 NULL

  2. 深度为 1 的节点，失败跳转节点是根节点

  3. 对于深度大于 1 的节点 A：

3.1. 假设节点 A 是通过节点 B 输入"a"跳转过来的，设 A 的失败跳转节点为 FailNode，将 FailNode 指向 B 的失效节点

3.2. 再判断，如果 FailNode 输入"a"有可跳转的节点或者 FailNode 指向的是根节点，则 A 的失败跳转节点就是 FailNode 输入"a"后所跳转的节点。否则将 FailNode 指向 FailNode 的失败跳转节点，再次执行 3.2 步骤。

根据上面的步骤，我们试试给上面的例子寻找失效跳转节点

  1. 根节点 [0] ，失败跳转节点=null

  1. 深度为 1 的节点[1]、[6]、[11]，失败跳转节点是根节点=[0]

  1. 深度为 2 的节点

    1. 节点[2]，是[1]输入 e 过来的，所以[2]的失败跳转节点先设置成[1]的失败跳转节点，也就是 [0]，由于[0]输入 e 后虽然没有目标节点，但它是根节点，所以[2]的失败跳转节点是[0]

    2. 节点[7]，是[6]输入 o 过来的，所以[7]的失败跳转节点先设置成[6]的失败跳转节点，也就是[0]，由于[0]输入 o 后虽然没有目标节点，但它是根节点，所以[7]的失败跳转节点是[0]

    3. 节点[12]，是[11]输入 a 过来的，所以[12]的失败跳转节点先设置成[11]的失败跳转节点，也就是[0]，由于[0]输入 a 后虽然没有目标节点，但它是根节点，所以[12]的失败跳转节点是[0]

  2. 深度为 3 的节点

    1. 节点[3]，是节点[2]输入 l 过来的，所以[3]的失败跳转节点先设置成[2]的失败跳转节点，也就是[0]，由于[0]输入 l 后虽然没有目标节点，但它是根节点，所以[3]的失败跳转节点是[0]

    2. 节点[8]，是节点[7]输入 r 过来的，所以[8]的失败跳转节点先设置成[7]的失败跳转节点，也就是[0]，由于[0]输入 r 后虽然没有目标节点，但它是根节点，所以[8]的失败跳转节点是[0]

    3. 节点[13]，是节点[12]输入 h 过来的，所以[13]的失败跳转节点先设置成[12]的失败跳转节点，也就是[0]，由于[0]输入 h 后跳转到[11]，所以[13]的失败跳转节点是[11]

  3. 深度为 4 的节点

    1. 节点[4]，是节点[3]输入 l 过来的，所以[4]的失败跳转节点先设置成[3]的失败跳转节点，也就是[0]，由于[0]输入 l 后虽然没有目标节点，但它是根节点，所以[4]的失败跳转节点是[0]

    2. 节点[9]，是节点[8]输入 l 过来的，所以[9]的失败跳转节点先设置成[8]的失败跳转节点，也就是[0]，由于[0]输入 l 后虽然没有目标节点，但它是根节点，所以[9]的失败跳转节点是[0]

    3. 节点[14]，是节点[13]输入 a 过来的，所以[14]的失败跳转节点先设置成[13]的失败跳转节点，也就是[11]，由于[11]输入 a 后跳转到[12]，所以[14]的失败跳转节点是[12]

  4. 深度为 5 的节点

    1. 节点[5]，是节点[4]输入 o 过来的，所以[5]的失败跳转节点先设置成[4]的失败跳转节点，也就是[0]，由于[0]输入 o 后虽然没有目标节点，但它是根节点，所以[5]的失败跳转节点是[0]

    2. 节点[10]，是节点[9]输入 d 过来的，所以[10]的失败跳转节点先设置成[9]的失败跳转节点，也就是[0]，由于[0]输入 d 后虽然没有目标节点，但它是根节点，所以[10]的失败跳转节点是[0]

最终，所有节点之间的跳转关系如下

graph LR 0--H-->1--e-->2--l-->3--l-->4--O-->5; 0--w-->6--O-->7--r-->8--l-->9--d-->10; 0--h-->11--a-->12--h-->13--a-->14; 1--fail-->0; 6--fail-->0; 11--fail-->0; 2--fail-->0; 7--fail-->0; 12--fail-->0; 3--fail-->0; 8--fail-->0; 13--fail-->11; 4--fail-->0; 9--fail-->0; 14--fail-->12; 5--fail-->0; 10--fail-->0;

3. 输入字符串进行关键字匹配

  1. 初始化 node 指向根节点，ch 指向字符串第一个字符，nextNode 为 null。

  1. 将 nextNode 指向 node 输入 ch 后跳转到的下一个节点

  1. 如果 nextNode 不为 null（存在下一个节点），则将 node 指向 nextNode，如果这个节点是结束节点，则将这个节点的数据取出放入结果集，若还有下一个字符，则将 ch 指向下一个字符，再次执行步骤 2，否则结束

  1. 如果 nextNode 为 null（不存在下一个节点），则将 node 指向 node 的失败跳转节点，如果这个节点不是根节点，则再次执行步骤 2。如果是根节点，则丢弃该字符，若还有下一个字符，则将 ch 指向下一个字符，再次执行步骤 2，否则结束

参考文章

AC算法在美团上单系统的应用

AC自动机算法_百度百科