AC自动机算法

前言

AC自动机，英文是Aho-Corasick automaton，该算法在1975年产生于贝尔实验室，是著名的多模匹配算法。

一个常见的例子就是给出n个单词，再给出一段包含m个字符的文章，让你找出有多少个单词在文章里出现过。

该算法借助Trie，即字典树，配以失配指针，在多模式串匹配中有着极高的效率。

算法的第一步是根据所有的模式串构建一颗字典树，然后就是添加失配指针，最后是模式匹配过程。

在只有一个模式串的时候，一般采用KMP算法，该算法核心在于next[]数组，该数组作用是当遇到当前字符不匹配的时候，模式串该如何移动。面对很多模式串的时候，如果对每一个模式串都采用KMP算法，这样虽然理论上可行，但是时间复杂度非常之高。

AC自动机中的Fail指针的作用也是类似next[]，不过这个失配指针的构建是根据模式串之间的公共后缀进行构建的。

算法实现

题目背景

洛谷P3808 AC自动机模版

题解

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
#define DESC (1000001)
#define TABLE_LEN (26)
#define KW_LEN (51)
#define NODE_LEN (1000006)
// #define NODE_LEN (16)
#define ROOT (0)
char dscri[NODE_LEN];
struct Node {
    int child[TABLE_LEN];
    int fail;
    char name;
    int cnt;
} AC[NODE_LEN];
int nodePtr = 1;
void addFail() {
    queue<int> myQueue;
    for (int i = 0; i < TABLE_LEN; i++)
        if (AC[ROOT].child[i]) myQueue.push(AC[ROOT].child[i]);
    while (!myQueue.empty()) {
        int father = myQueue.front();
        myQueue.pop();
        for (int i = 0; i < TABLE_LEN; i++) {
            int childId = AC[father].child[i];
            if (childId) {
                // 若AC[father].fail节点没有子节点i  则AC[childId].fail为0
                // 即根节点
                AC[childId].fail = AC[AC[father].fail].child[i];
                myQueue.push(childId);
            } else {
                AC[father].child[i] = AC[AC[father].fail].child[i];
            }
        }
    }
}
void trieInsert(const char *word) {
    int now = ROOT, len = strlen(word);
    for (int i = 0; i < len; i++) {
        int c = word[i] - 'a';
        if (!AC[now].child[c]) {
            AC[now].child[c] = nodePtr++;
            AC[AC[now].child[c]].name = c + 'a';
        }
        now = AC[now].child[c];
    }
    AC[now].cnt++;
}
int acQuery() {
    int len = strlen(dscri), sum = 0;
    int now = ROOT;
    for (int i = 0; i < len; i++) {
        int c = dscri[i] - 'a';
        now = AC[now].child[c];
        // 循环求解是因为fail指向的节点也和该节点有相同部分
        for (int j = now; j && AC[j].cnt != -1; j = AC[j].fail) {
            sum += AC[j].cnt;
            AC[j].cnt = -1;
        }
    }
    return sum;
}
int main() {
    int caseNum, n;
    char p[NODE_LEN];
    memset(AC, 0, sizeof(AC));

    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("%s", p);
        trieInsert(p);
    }
    addFail();
    scanf("%s", dscri);
    printf("%d\n", acQuery());
    return 0;
}