产生

全称Aho-Corasick automaton，该算法在1975贝尔实验室年产，是著名的多模匹配算法。

用途

• 字符串的匹配
• 多串匹配问题

例如，给几个单词 acbs，asf，dsef，

再给一篇很长的文章，acbsdfgeasf，

问这篇文章中出现了多少个单词，或者出现了多少个单词。

实现原理

KMP Trie树(字典树)

KMP，不懂的请出去右转https://blog.csdn.net/qq_38946354/article/details/97234737，是一种没有多余回溯的算法。

Trie字典树是一种用于快速检索的多叉树数据结构。用于保存大量字符串。它的优点是利用字符串的公共前缀来节省存储空间。实现方法可参考https://blog.csdn.net/qq_38946354/article/details/99902661

AC自动机的关键是在 Trie树上，加了 fail指针（失配指针）。fail 指针的用途就像 KMP中的 Next当字符串不匹配时，确定转移节点。

具体实现

构造字典树

struct Trie {     Trie *next[26];     Trie *fail;     int num;     Trie(){         for (int i = 0; i < 26; i  )             next[i] = NULL;         fail = NULL;         num = 0;     } }; char P[maxp]; char T[maxt]; Trie *q[maxq]; void insert(Trie *root, char *s) //字典树上 插入字符串s {     Trie *p = root;     for (int i = 0; s[i] != '\0'; i  ){         int c = s[i] - 'a';         if (p->next[c] == NULL){             p->next[c] = new Trie;         }         p = p->next[c];     }     p->num  ; }

构建失配指针

在构造完Tire树后，下一步就是构造失败指针。构造失败指针的过程总结为一句话：这个节点上的字母是 C，沿着父亲节点的失配指针走，直到它到达一个节点，它的子结点也有字母 C 的节点。然后将当前节点的失败指针指向字母 C 的儿子。假如一直到 root 如果找不到，指向失配指针 root。具体操作起来只需要：先把root加入队列（root失配指针指向自己或 NULL），在那之后，我们把它所有的儿子都加入了队列，每次处理一个点。

void build_ac_automation(Trie *root) //利用BFS创建AC自动机 {     int head = 0, tail = 0;  //队列首尾指针     q[tail  ] = root;     while (head != tail){         Trie *temp = q[head  ];         for (int i = 0; i < 26; i  ){  ///遍历队头元素的子结点             if (temp->next[i] != NULL){                 Trie *p = temp->fail;                 while (p != NULL){  //只有根结点的失配指针为 NULL                     if (p->next[i] != NULL){  //沿着失配指针回去，直到某个节点，                         temp->next[i]->fail = p->next[i];  //它有一个字母a' i的子结点                         break;                     }                     p = p->fail;  ///沿着失配指针一直在寻找                 }                 if (p == NULL)                     temp->next[i]->fail = root; //p==NULL 在沿着失配指针回去的过程中，没有找到合适的结点                 q[tail  ] = temp->next[i];  ///每处理一个结点，让结点的所有子节点依次入队             }         }     } }

为什么这种方法可行，可以保证 root 跳转位置的字符串长度小于当前匹配的字符串长度，与当前匹配的字符串后缀完全相同，长度最大？

显然，当我们构建失配指针时，我们从当前节点的父节点失配指针开始，因为 Trie 树压缩了所有单词中相同的前缀，所以所有不匹配的指针都不可能在同一水平上跳转（到达另一个与自己深度相同的节点），因为如果在同一水平上跳转，很明显，跳转到达的节点肯定不是当前匹配字符串后缀的一部分，否则两个节点将合并为一个，因此，跳转只能到达比当前深度小的节点，由于跳转是从当前节点的父节点开始的，因此可以保证从 root 跳转到位置的字符串长度小于当前匹配的字符串长度。另一方面，我们可以比较 KMP 求 NEXT 在数组中寻求最大匹配数量的想法，这种想法是 AC 自动机的体现是，当构建失败指针时，不断返回以前的跳转位置，然后判断跳转位置的下一个字符是否包含当前字符。如果是，将失败指针连接到跳转位置，若跳转位置指向 NULL 这意味着当前匹配的字符在当前深度之前没有出现，不能匹配任何跳转位置，如果发现第一个跳转位置的下一个字符包含当前字符的跳转位置，必须达到最大长度，这是因为当前匹配的其他字符必须高于当前字符的跳转位置深度，即使可以，这样的跳转位置也不会是最大的（最后一个字符的深度小于最后一个字符的深度，最后一个字符的最后一个字符在第一个可行的跳转位置，串必须更短）。

匹配

匹配过程分为两种情况：（1）当前字符匹配，表示从当前节点沿树边有一条路径到达目标字符。此时，只需沿路径到下一个节点继续匹配，目标字符串指针移动到下一个字符继续匹配；（2）如果当前字符不匹配，则继续匹配当前节点失败指针指向的字符。匹配过程随指针指向root结束。重复这两个过程中的任何一个，直到模式串结束。

int query(Trie *root, char *T) {     int ans = 0;     Trie *p = root;     for (int i = 0, len = strlen(T); i < len; i  ){         int c = T[i] - 'a';         while (p->next[c] == NULL && p != root) //如果当前结点没有字符 T[i] 儿子目前不是根节点             p = p->fail;                        ///沿着失配指针回去，直到找到合适的节点或根结点         if (p->next[c] != NULL)             p = p->next[c];         Trie *temp = p;         while (temp != NULL)             p = p->next[c];         Trie *temp = p;         while (temp != root && temp->num != -1){ ///沿着失配指针回去，直到根结点             ans  = temp->num; //如果当前节点num不为 0，说明以当前节点字母结尾的单词出现了                               ///这个单词是以上循环的结点字母为结尾的单词子集             temp->num = -1;   //标记 num 为-1，避免重复计算             temp = temp->fail;         }     }     return ans; }

完整代码

#include <cstdio>
#include <cstring>
using namespace std;
const int maxp = 50 + 7;
const int maxt = 1000000 + 7;
const int maxq = 10000 * maxp;
struct Trie
{
    Trie *next[26];
    Trie *fail;
    int num;
    Trie(){
        for (int i = 0; i < 26; i++)
            next[i] = NULL;
        fail = NULL;
        num = 0;
    }
};
char P[maxp];
char T[maxt];
Trie *q[maxq];
void insert(Trie *root, char *s) //在字典树上 插入字符串s
{
    Trie *p = root;
    for (int i = 0; s[i] != '\0'; i++){
        int c = s[i] - 'a';
        if (p->next[c] == NULL){
            p->next[c] = new Trie;
        }
        p = p->next[c];
    }
    p->num++;
}
void build_ac_automation(Trie *root) //利用BFS创建AC自动机
{
    int head = 0, tail = 0;  //队列首尾指针
    q[tail++] = root;
    while (head != tail){
        Trie *temp = q[head++];
        for (int i = 0; i < 26; i++){  //遍历队头元素的子结点
            if (temp->next[i] != NULL){
                Trie *p = temp->fail;
                while (p != NULL){  //只有根结点的失配指针为 NULL
                    if (p->next[i] != NULL){  //顺着失配指针往回走，直至某个节点，
                        temp->next[i]->fail = p->next[i];  //其拥有一个字母为'a'+i的子结点
                        break;
                    }
                    p = p->fail;  //沿着失配指针一直找
                }
                if (p == NULL)
                    temp->next[i]->fail = root; //p==NULL 说明顺着失配指针往回走的过程中没有找到合适的结点
                q[tail++] = temp->next[i];  //每处理一个结点，都让该结点的所有子节点依次入队
            }
        }
    }
}
int query(Trie *root, char *T)
{
    int ans = 0;
    Trie *p = root;
    for (int i = 0, len = strlen(T); i < len; i++){
        int c = T[i] - 'a';
        while (p->next[c] == NULL && p != root) //若当前结点的没有一个字符为 T[i] 的儿子且当前不是根节点
            p = p->fail;                        //顺着失配指针往回走，直至找到合适的节点或根结点为止
        if (p->next[c] != NULL)
            p = p->next[c];
        Trie *temp = p;
        while (temp != root && temp->num != -1){ //顺着失配指针往回走，一直到根结点
            ans += temp->num; //若当前节点的num不为 0，则说明以当前节点字母结尾的单词出现过
                              //此单词是以上一次循环的结点字母为结尾的单词的子集
            temp->num = -1;   //标记 num 为-1，避免重复计算
            temp = temp->fail;
        }
    }
    return ans;
}
int main()
{
    int t, n;
    scanf("%d", &t);
    while (t--){
        Trie *root = new Trie;
        scanf("%d", &n);
        getchar();
        for (int i = 0; i < n; i++){
            gets(P);
            insert(root, P);
        }
        build_ac_automation(root);
        gets(T);
        printf("%d\n", query(root, T));
    }
    return 0;
}

 

部分参考来自https://blog.csdn.net/liu940204/article/details/51347064