题目描述

算法

第一次写题解。个人理解有限，如有错误和补充，欢迎补充。

参考

算法提高课

C++ 代码

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=1000010;

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

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; //记录每个单词的结尾所在的地方
}

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 j=tr[t][i];
            if(!j) tr[t][i]=tr[ne[t]][i];
            else
            {
                ne[j]=tr[ne[t]][i];
                q[++tt]=j;
            }
        }
    }
}


int main()
{
    cin>>n;

    for(int i=1;i<=n;i++)
    {
        cin>>str;
        insert(i);
    }

    build();

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

    for(int i=1;i<=n;i++) cout<<f[id[i]]<<endl;

    return 0;
}