原题链接： 【模板】AC自动机（加强版）

题目描述

给出 $N$个长度 $\leq 150$ 的模式串，再给出一个长度 $\leq 10^6$ 的长串，求在长串中出现次数最多的模式串
多组测试数据，$N \leq 70$

AC自动机 树形DP

建出fail树，遍历一下长串记录贡献，跑个树形DP

时间复杂度 $O(线性)$

C++ 代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>

using namespace std;

const int N = 150 * 72, M = 1e6 + 10;

int tr[N][26], ne[N], idx;

int id[160];
char str[160][72], s[M];

void insert(char s[], int x)
{
    int u = 0;
    for(int i = 0; s[i]; i ++)
    {
        int k = s[i] - 'a';
        if(!tr[u][k])  tr[u][k] = ++ idx;
        u = tr[u][k];
    }
    id[x] = u;
}

vector<int> v[N];
int q[N];

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 u = q[hh ++];
        v[ne[u]].push_back(u);

        for(int k = 0; k < 26; k ++)
        {
            int j = tr[u][k];
            if(!j)  tr[u][k] = tr[ne[u]][k];
            else
            {
                ne[j] = tr[ne[u]][k];
                q[++ tt] = j;
            }
        }
    }
}

int f[N];
void dfs(int u)
{
    for(int j : v[u])
    {
        dfs(j);
        f[u] += f[j];
    }
}

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

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

        for(int i = 0; i <= idx; i ++)  v[i].clear();
        build();

        scanf("%s", s);
        for(int i = 0, j = 0; s[i]; i ++)
        {
            int k = s[i] - 'a';
            j = tr[j][k];
            f[j] ++;
        }

        dfs(0);

        int res = 0;
        for(int i = 0; i < n; i ++)  res = max(res, f[id[i]]);

        printf("%d\n", res);
        for(int i = 0; i < n; i ++)
            if(f[id[i]] == res)  puts(str[i]);
    }
    return 0;
}