洛谷P3966 [TJOI2013]单词 题解

题目链接：P3966 [TJOI2013]单词

题意：

小张最近在忙毕设,所以一直在读论文。一篇论文是由许多单词组成但小张发现一个单词会在论文中出现很多次，他想知道每个单词分别在论文中出现了多少次。

\(1 \leq n \leq 200\)，单词总长度不超过 \(10^6\)。

瞎搞做法能跑到最优解前3页也是有趣

这个文章看样例应该是单词间有空格的

于是我们就把所有单词全部加上去，用#分隔

然后就变成 P5357 AC自动机二次加强版 了

具体的就是把暴力跳fail数组改成topo排序更新

时间复杂度 \(O(26 \times \sum s_i)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <queue>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(205)
#define L (int)(1e6+215)

int n,f[N],fail[L],val[L],in[L],ans[N];
string s,t;
struct Trie
{
    queue<int> q;
    int tot,trie[L][26],ed[L];
    void insert(string s,int id)
    {
        int u=0;
        for(int i=0; i<s.size(); i++)
        {
            int c=s[i]-'a';
            if(!trie[u][c])trie[u][c]=++tot;
            u=trie[u][c];
        }
        if(!ed[u])ed[u]=id;
        f[id]=ed[u];
    }
    void build()
    {
        for(int i=0; i<26; i++)
            if(trie[0][i])q.push(trie[0][i]);
        while(!q.empty())
        {
            int u=q.front();q.pop();
            for(int i=0; i<26; i++)
            {
                if(trie[u][i])
                {
                    fail[trie[u][i]]=trie[fail[u]][i];
                    ++in[trie[fail[u]][i]];
                    q.push(trie[u][i]);
                }else trie[u][i]=trie[fail[u]][i];
            }
        }
    }
    void AC()
    {
        int u=0;
        for(int i=0; i<t.size(); i++)
        {
            if(t[i]=='#')u=0;
            else u=trie[u][t[i]-'a'];
            ++val[u];
        }
        for(int i=1; i<=tot; i++)
            if(!in[i])q.push(i);
        while(!q.empty())
        {
            u=q.front(); q.pop();
            if(ed[u])ans[ed[u]]=val[u];
            val[fail[u]]+=val[u];
            if(!--in[fail[u]])q.push(fail[u]);
        }
    }
}tr;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1; i<=n; i++)
    {
        cin >> s; t+=s+"#";
        tr.insert(s,i);
    }
    tr.build(); tr.AC();
    for(int i=1; i<=n; i++)
        cout << ans[f[i]] << '\n';
    return 0;
}