AC 自动机

1、AC 自动机的原理

AC 自动机：Aho-Corasick automation，该算法在 1975 年产生于贝尔实验室，是著名的多模式串匹配算法之一。一个常见的例子就是给出 n 个单词，再给出一段包含 m 个字符的文章，让你找出有多少个单词在文章里出现过。

要搞懂 AC 自动机，先得有字典树 Trie 和 KMP 模式匹配算法的基础知识。KMP 算法是单模式串的字符匹配算法，AC 自动机是多模式串的字符匹配算法。

AC 自动机的构造：

1. 构造一棵 Trie，作为 AC 自动机的搜索数据结构。
2. 构造 next 指针，使当前字符失配时跳转到具有最长公共前后缀的字符继续匹配。如同 KMP 算法一样，AC 自动机在匹配时如果当前字符匹配失败，那么利用 next 指针进行跳转。由此可知如果跳转，跳转后的串的前缀，必为跳转前的模式串的后缀并且跳转的新位置的深度（匹配字符个数）一定小于跳之前的节点。所以我们可以利用 bfs 在 Trie 上面进行 next 指针的求解。

如果要求 k 号结点的 next 值：

(1) 看 k 号结点父节点的 next 值 → j
(2) 判断 j 是否有某个子结点的值和 k 号结点值相同
　　A、有，next[k] 指向对应的子结点
　　B、没有，j = next[j] 继续回跳，直到跳到根

1. 扫描主串进行匹配。

2. AC 自动机相当于：Trie + KMP 的组合。

3. AC 自动机，可以优化为 Trie 图。

完成任务：

3099. 搜索关键词

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 10010, S = 55, M = 1000010;

int n;
int tr[N * S][26], cnt[N * S], idx;
char str[M];
int q[N * S], ne[N * S];

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int t = str[i] - 'a';
        if (!tr[p][t]) tr[p][t] = ++ idx;
        p = tr[p][t];
    }
    cnt[p] ++ ;
}

void build()
{
    int hh = 0, tt = -1;
    for (int i = 0; i < 26; i ++ )
        if (tr[0][i])
            q[ ++ tt] = tr[0][i];

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = 0; i < 26; i ++ )
        {
            int p = tr[t][i];
            if (!p) tr[t][i] = tr[ne[t]][i];
            else
            {
                ne[p] = tr[ne[t]][i];
                q[ ++ tt] = p;
            }
        }
    }
}


// build: 求每个结点的 next 值， 没有带回跳优化版本
void build() {
    int h = 1, t = 0; // 队列头尾指针，q[1..t] 存储节点，初始为空

    // 将根节点（编号为0）下面的第一层结点入队
    // 因为这一层的结点的 next 值都是 0（指向根）
    for (int i = 0; i < 26; i++) {
        if (ch[0][i]) {
            q[++t] = ch[0][i];
        }
    }

    // bfs 计算每一层结点的 next 值
    while (h <= t) {
        int f = q[h]; // 当前父节点编号

        for (int i = 0; i < 26; i++) {
            if (ch[f][i]) {
                int c = ch[f][i]; // 获取子结点编号

                // 获取父节点 f 的 next 值
                int j = ne[f];
                // 沿着 next 链回跳，直到找到有字符 i 子节点的节点，或回到根
                while (j && !ch[j][i]) {
                    j = ne[j];
                }
                // 如果找到匹配的子节点，则 next[c] 指向它；否则指向根（j=0）
                if (ch[j][i]) {
                    ne[c] = ch[j][i];
                } else {
                    ne[c] = 0; // 可省略，因 ne 数组已初始化为 0
                }

                q[++t] = c; // 子节点入队
            }
        }
        h++; // 出队
    }
}


int main()
{
    int T;
    scanf("%d", &T);
    while (T -- )
    {
        memset(tr, 0, sizeof tr);
        memset(cnt, 0, sizeof cnt);
        memset(ne, 0, sizeof ne);
        idx = 0;

        scanf("%d", &n);
        for (int i = 0; i < n; i ++ )
        {
            scanf("%s", str);
            insert();
        }

        build();

        scanf("%s", str);

        int res = 0;
        for (int i = 0, j = 0; str[i]; i ++ )
        {
            int t = str[i] - 'a';
            //下面两行：没有带回跳优化版本
            //while(j && !tr[j][t])j= ne[j]; //当匹配不上时，j要回跳
            //if(tr[j][t])j= tr[j][t];//能匹配，j跳到子结点

            j = tr[j][t]; // 注意：上面两句可以直接优化为，这一句

            int p = j;
            while (p)
            {
                res += cnt[p];
                cnt[p] = 0;
                p = ne[p];
            }
        }

        printf("%d\n", res);
    }

    return 0;
}

版本二：优化 j=ne[j] 回跳的过程，保证时间是线性的。

(1) 如果回跳一次能匹配，则 ne[c] = ch[ne[f]][i]； (2) 如果匹配不上，理论上要回跳多次，但是我们可以通过将不存在的子结点的 next 值存储到邻接矩阵的方法，使得所有结点的所有子结点都存在，这样就不用回跳多次。

// bfs: 求每个结点的 next 值
void bfs() {
    int h = 1, t = 0; // 默认队列为空（使用数组模拟队列，下标从1开始）

    // 将根节点下面的第一层结点入队
    // 因为这一层的结点的 next 值都是 0（即根节点）
    for (int i = 0; i < 26; i++) {
        if (ch[0][i]) {
            q[++t] = ch[0][i];
        }
    }

    // bfs 计算每一层结点的 next 值
    while (h <= t) {
        int f = q[h]; // 当前父节点编号

        for (int i = 0; i < 26; i++) {
            if (ch[f][i]) {
                int c = ch[f][i]; // 获取子结点编号
                ne[c] = ch[ne[f]][i]; // 直接利用父节点的 ne 值转移
                q[++t] = c; // 入队
            } else {
                // 如果结点 f 不存在子结点 i，
                // 则将其重定向为 ne[f] 对应的子结点（Trie 图优化）
                ch[f][i] = ch[ne[f]][i];
            }
        }
        h++; // 出队
    }
}

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com