Keywords Search HDU - 2222 ac自动机模板题

//ac自动机 可以优化成 trie图
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 10010, S = 55, M = 1000010;
int n;
//tire              以每个节点结尾的单词数量
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];
    }
    //以p结尾的单词数量++
    cnt[p] ++ ;
}
//构建ac自动机
//宽搜
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 ++ ) {
            //p是
            //p对应kmp中的i
            int p = tr[t][i];
            //如果不存在
            //指向父节点的next指针的位置
            //相当于直接跳到应该走到的位置，避免多次跳，降低时间复杂度
            if (!p)
                tr[t][i] = tr[ne[t]][i];
            //如果存在
            else {
                //等价while循环
                ne[p] = tr[ne[t]][i];
                //再加到队列中
                q[ ++ tt] = p;
            }
        }
    }
}
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();
        }
        //构建ac自动机
        build();
        scanf("%s", str);
        int res = 0;
        //匹配和原来kmp差不多
        //j从根节点传进来
        for (int i = 0, j = 0; str[i]; i ++ ) {
            //字母
            int t = str[i] - 'a';
            j = tr[j][t];
            int p = j;
            while (p) {
                res += cnt[p];
                //每个单词只能加一次，所以要清零
                cnt[p] = 0;
                //往下
                p = ne[p];
            }
        }
        printf("%d\n", res);
    }
    return 0;
}

Keywords Search HDU - 2222 ac自动机模板题

原文：https://www.cnblogs.com/QingyuYYYYY/p/12522621.html