题目描述

C++ 代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
using namespace std;

const int N=1e6+10;

int n;
int tr[N][26],f[N],idx;
int q[N],ne[N];
char str[N];
int id[210];

//ne代表最大能匹配的 那个结点， 最终会回到0，不过，在0之前，一定会回到该单词本身。

void insert(int x)
{
    int p=0;
    for(int i=0;str[i];i++)
    {
        int t=str[i]-'a';
        if(!tr[p][t]) tr[p][t]=++idx;
        p=tr[p][t];
        f[p]++;
    }
    id[x]=p;        //idx记录本次插入中的末尾结点是哪个。
}                   //因为以后所有后缀记录的f值都会加到它上面去。

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 t=q[hh++];
        for(int i=0;i<26;i++)
        {
            int &p=tr[t][i];
            if(!p) p=tr[ne[t]][i];
            else
            {
                ne[p]=tr[ne[t]][i];
                q[++tt]=p;
            }
        }
    }

}

int main()
{
    scanf("%d",&n); 

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

    build();

    for(int i=idx-1;i>=0;i--) f[ne[q[i]]] += f[q[i]];

    for(int i=0;i<n;i++) printf("%d\n",f[id[i]]);

    return 0;
}