3796.【模板】AC自动机（加强版）

P3796.【模板】AC 自动机

题目描述：

多组输入数据，第一行一个正整数 $ N $ ，表示共有 $ N $ 个模式串，接下来 $ N $ 行，每行一个模式串 $ s_i $ ，下一行是待匹配的文本串 $ T $ ，保证不会出现两个相同的模式串。当输入 $ N = 0 $ 时输入结束。

对于每组输入数据，第一行输出模式串最多出现的次数，接下来若干行每行输出一个出现次数最多的模式串。

数据范围：
$ 1\le N \le 150,1\le s_i\le 70,1\le T_i\le 10^6 $

题解：

需要统计每个模式串在文本串中出现的次数，求出最大次数之后，然后遍历所有的模式串，如果出现的次数等于最大次数则输出。

需要在插入的时候把 $ id $ 也存进去，记录模式串对应的点的 $ id $ 。

在查询时，如果遇到了一个模式串，则将其出现的次数加一，同时更新最大次数。详细实现看代码。

和前一道AC自动机题目不同，前一个需要求有多少个模式串出现过，不能出现重复，因此会把出现过的字符串重新置为未出现过。这个题目需要统计次数，可以多次出现。

代码：

using namespace std;
using namespace FAST_IO;
const ll mod = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const ll INF_LL = 0x3f3f3f3f3f3f3f3f;
const double eps = 1e-5;
const int maxn = 1e6 + 10;
const int maxm = 7e1 + 10;
int t, n, m, k;
struct ACTrie
{
    const static int M = 26;
    const static int maxn = 1e6 + 10;
    int next[maxn][M] = {}, fail[maxn] = {}, cnt = 0;
    int exist[maxn] = {};
    int id[maxn]; // 以u结尾的字符串对应的输入id
    int times[maxn] = {};
    queue<int> q;

    void init()
    {
        for (int i = 0; i < maxn; ++i)
        {
            for (int j = 0; j < M; ++j)
            {
                next[i][j] = 0;
            }
            fail[i] = 0;
            exist[i] = 0;
            id[i] = -1;
            times[i] = 0;
        }
        cnt = 0;
    }
    void insert(char *s, int index)
    {
        int now = 0, len = strlen(s);
        for (int i = 0; i < len; ++i)
        {
            int c = s[i] - 'a';
            if (!next[now][c])
                next[now][c] = ++cnt;
            now = next[now][c];
        }
        exist[now]++;
        id[now] = index;
    }

    void build()
    {

        for (int i = 0; i < M; ++i)
        {
            if (next[0][i])
            {
                fail[next[0][i]] = 0;
                q.push(next[0][i]);
            }
        }
        while (q.size())
        {
            int u = q.front();
            q.pop();
            for (int i = 0; i < M; ++i)
            {
                if (next[u][i])
                {
                    fail[next[u][i]] = next[fail[u]][i];
                    q.push(next[u][i]);
                }
                else
                    next[u][i] = next[fail[u]][i];
            }
        }
    }

    int query(char *s)
    {
        int now = 0, len = strlen(s), ans = 0;
        for (int i = 0; i < len; ++i)
        {
            int c = s[i] - 'a';
            now = next[now][c];
            for (int j = now; j; j = fail[j])
            {
                if (id[j] != -1)
                {
                    times[id[j]]++;
                    ans = max(ans, times[id[j]]);
                }
            }
        }
        return ans;
    }
};
char a[maxn][maxm];
char s[maxn];
int main()
{
// #define COMP_DATA
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif
    ios::sync_with_stdio(false);
    cin.tie(0);
    ACTrie trie;
    while (cin >> n && n)
    {
        trie.init();
        for (int i = 0; i < n; ++i)
        {
            cin >> a[i];
            trie.insert(a[i], i);
        }
        cin >> s;
        trie.build();
        int ans = trie.query(s);
        cout << ans << endl;
        for (int i = 0; i < n; ++i)
        {
            if (trie.times[i] == ans)
            {
                cout << a[i] << endl;
            }
        }
    }
    return 0;
}