题解 P3796 【【模板】AC自动机（加强版）】

· · 题解

ac自动机裸题

虽说是加强版,不过其实就是稍微换了下求的东西,还是很裸的

具体改动的地方在代码里给出

上菜:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int maxn = 300000+5;
const int SIGMA_SIZE = 26;
int maxx = 0;//得出的最大大数目答案
char p[200][105];//用来输出字符答案
int ans[200];//唯一加的地方,用来存答案
char T[1000000+5];
queue <int> qe;
//ac自动机 机体qvq ps:感觉这种自动机写起来最好看(雾
struct AC_automata
{
    int ch[maxn][26], val[maxn], f[maxn], cnt = 0;
    void clear()//给数组清零
    {
        cnt = maxx = 0;
        for(int i = 0; i < maxn; ++i)
        {
            val[i] = f[i] = 0;
            for(int j = 0; j < 26; ++j)ch[i][j] = 0;
        }
        memset(ans, 0, sizeof ans);
    }
    void insert(char *s, int num)
    {
        int now = 0;
        for(int i = 0; i < strlen(s); i++)
        {
            if(!ch[now][s[i]-'a'])ch[now][s[i]-'a'] = ++cnt;
            now = ch[now][s[i]-'a'];
        }
        val[now] = num;
    }
    void getFail()
    {
        for(int i = 0; i < SIGMA_SIZE; i++)if(ch[0][i])qe.push(ch[0][i]);
        while(!qe.empty())
        {
            int u = qe.front();qe.pop();
            for(int i = 0; i < SIGMA_SIZE; i++)
            {
                if(ch[u][i]){f[ch[u][i]] = ch[f[u]][i];qe.push(ch[u][i]);}
                else ch[u][i] = ch[f[u]][i];
            }
        }
    }
    void find()
    {
        int len = strlen(T), now = 0;
        for(int i = 0; i < len; i++)
        {
            now = ch[now][T[i]-'a'];
            for(int t = now; t; t = f[t]){if(val[t]){ans[val[t]]++;if(t!=0)maxx = max(maxx,ans[val[t]]);}}
        }
    }
}AC;
int n;
int main()
{
    while(scanf("%d", &n) == 1 && n)
    {
        AC.clear();
        for(int i = 1; i <= n; ++i)
            scanf(" %s", p[i]),AC.insert(p[i], i);
        AC.getFail();
        scanf("%s", T);
        AC.find();
        printf("%d\n", maxx);
        for(int i = 1; i <= n; ++i)if(ans[i] == maxx)printf("%s\n", p[i]);
        //如果找到和答案一样数目的单词就输出
    }
    return 0;
}