HDU 2222 Keywords Search

AC自动机

I have a Trie

I have a KMP

Uh, AC自动机！

原理

AC自动机是以Trie的多模式匹配为基础，取了类似于KMP中nxt数组的作用，避免了Trie每次匹配失败的回溯过程，缩短了时间

步骤

1. 建树（Trie）
2. BFS构造fail指针 (这里以及很多其他地方的“指针”是广义上的指针，只是一个int类型的变量存了一个值)
3. 模式匹配（查询）

学习博客： https://www.cnblogs.com/TheRoadToTheGold/p/6290732.html

理解博客： https://blog.csdn.net/bestsort/article/details/82947639

(这篇博客里的模板没有初始化函数，做题会TLE，是的，没初始化也会TLE！)

（在Trie里，字母是存在 ‘边’ 上的，而他写在节点上了）

模板出处：https://www.cnblogs.com/KonjakJuruo/p/5686398.html

Code

#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const int N =  2 * 1e6 + 9;

int cnt = 0, fail[N], sum[N], trie[N][26];

void clean(int num)
{
    sum[num] = 0, fail[num] = 0;
    memset(trie[num], 0, sizeof(trie[num]));
}

void plug(char * s)
{
    int root = 0;
    for(int i = 0; s[i]; ++i)
    {
        int x = s[i] - 'a';
        if(!trie[root][x])
            {
                ++cnt;
                clean(cnt);
                trie[root][x] = cnt;
            }
        root = trie[root][x];
    }
    sum[root]++;
}

void getfail()
{
    queue<int> q;
    for(int i = 0; i < 26; ++i)
        if(trie[0][i])
            fail[ trie[0][i] ] = 0, q.push(trie[0][i]);

    while(!q.empty())
    {
        int now = q.front();
        q.pop();

        for(int i = 0; i < 26; ++i)
        {
            if(trie[now][i])
            {
                fail[ trie[now][i] ] = trie[ fail[now] ][i];
                q.push(trie[now][i]);
            }
            else
                trie[now][i] = trie[ fail[now] ][i];
        }
    }
}

int query(char * s)
{
    int now = 0, ans = 0, len = strlen(s);
    for(int i = 0; i < len; ++i)
    {
        now = trie[now][ s[i] - 'a' ];
        for(int j = now; j && sum[j] != -1; j = fail[j])
        {
            ans += sum[j];
            sum[j] = -1;///标记以示遍历过
        }
    }
    return ans;
}

char s[1000005];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n;
        scanf("%d", &n);
        clean(0);                       ///没有这个会TLE
        for(int i = 0; i < n; ++i)
        {
            scanf("%s", s);
            plug(s);
        }
        getfail();
        scanf("%s", s);
        cout << query(s) << '\n';
    }
    return 0;
}