样例输出

7
4
2

代码：

#include<bits/stdc++.h>
using namespace std;
const int N=1000005,M=2000005;
struct node
	{
	int nxt[26],end,fail,ans;
	}a[M];
int cnt=0,l,pcnt=0,z[N],fa[N],in[N],vis[N];
string s[N],p;
map<string,int>mp;
void init(){memset(a,0,sizeof a);memset(z,0,sizeof z);memset(fa,0,sizeof fa);cnt=pcnt=0;}
void ins(int w)
	{
	int now=0;
	for(int i=0;i<l;i++)
		{
		int ch=s[w][i]-'a';
		if(a[now].nxt[ch]==0)a[now].nxt[ch]=++cnt;
		now=a[now].nxt[ch];
		}
	a[now].end=w;
	}
void gf()
	{
	queue<int>q;
	for(int i=0;i<26;i++)
		{
		if(a[0].nxt[i])q.push(a[0].nxt[i]);
		}
	while(!q.empty())
		{
		int now=q.front();q.pop();
		for(int i=0;i<26;i++)
			{
			if(a[now].nxt[i])
				{
				a[a[now].nxt[i]].fail=a[a[now].fail].nxt[i];
				in[a[a[now].nxt[i]].fail]++;
				q.push(a[now].nxt[i]);
				}
			else a[now].nxt[i]=a[a[now].fail].nxt[i];
			}
		}
	}
void query()
	{
	int u=0;
	for(int i=0;i<l;++i){u=a[u].nxt[p[i]-'a'];a[u].ans++;}						//直接打上标记
	}
void topu()
	{
	queue<int>q;
    for(int i=1;i<=cnt;i++)
    	if(in[i]==0)q.push(i);
    while(!q.empty())
		{
        int u=q.front();q.pop();
		vis[a[u].end]=a[u].ans;
        int v=a[u].fail;in[v]--;
        a[v].ans+=a[u].ans;
        if(in[v]==0)q.push(v);
    	}
	}
int main()
	{
	init();
	int n;cin>>n;
	for(int i=1;i<=n;i++)
		{
		cin>>s[i];l=s[i].size();fa[i]=i;
		if(mp[s[i]])fa[i]=mp[s[i]];
		else {mp[s[i]]=i;ins(i);}
		}
	gf();
	for(int i=1;i<=n;i++)p=p+s[i]+' ';
	l=p.size();
	query();topu();
	for(int i=1;i<=n;i++)cout<<vis[fa[i]]<<'\n';
	return 0;
	}

玄关