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

链接🔗

「TJOI2013」 单词

题解

如果一个单词能匹配，那么它的fail也能匹配，然后要按队列进出顺序进行统计次数

代码

#include <cstdio>
#include <queue>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;
const int maxd = 1e7+10;
char str[maxd];
struct 
{
    int ch[maxd][26],fail[maxd],cnt[maxd],ans[maxd],tot;
    stack<int> stk;
    void insert(char *str,int k)
    {
        int p = 0;
        for(int i=0;str[i];i++)
        {
            if(!ch[p][str[i]-'a']) ch[p][str[i]-'a'] = ++tot;
            p = ch[p][str[i]-'a'];
            ans[p]++;
        }
        cnt[k] = p;
    }
    void build()
    {
        memset(fail,0,sizeof(fail));
        queue<int> que;
        for(int i=0;i<26;i++) if(ch[0][i])
        {
            que.push(ch[0][i]);
            stk.push(ch[0][i]);
        }
        while(!que.empty())
        {
            int p = que.front();que.pop();
            for(int i=0;i<26;i++)
            {
                if(ch[p][i])
                {
                    fail[ch[p][i]] = ch[fail[p]][i];
                    que.push(ch[p][i]);
                    stk.push(ch[p][i]);
                }
                else ch[p][i] = ch[fail[p]][i];
            }
        }
    }
    void solve()
    {
        while(!stk.empty())
        {
            int k = stk.top();
            ans[fail[k]] += ans[k];
            stk.pop();
        }
    }
}AC;
int main()
{
    // freopen("a.in","r",stdin);
    // freopen("k.out","w",stdout);
    int last = 0,n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s",str);
        AC.insert(str,i);
    }
    AC.build();
    AC.solve();
    for(int i=1;i<=n;i++)
        printf("%d\n",AC.ans[AC.cnt[i]]);
    return 0;
}