题解

#include <bits/stdc++.h>
using namespace std;
#define maxn 200010
#define ll long long

int T,n,ans[maxn];
char s[maxn];
struct state{
	int len,link,next[26],belong;
}st[maxn];
int id=0,last,now,p,q;
void extend(int x,int be)
{
	now=++id;
	st[now].len=st[last].len****t[now].belong=be;
	for(p=last;p!=-1&&!st[p].next[x];p=st[p].link)st[p].next[x]=now;
	if(p!=-1)
	{
		q=st[p].next[x];
		if(st[p].len+1==st[q].len)st[now].link=q;
		else
		{
			int clone=++id;
			st[clone]=st[q];st[clone].len=st[p].len+1;
			for(;p!=-1&&st[p].next[x]==q;p=st[p].link)st[p].next[x]=clone;
			st[q].link=st[now].link=clone;
		}
	}
	last=now;
}
struct edge{int y,next;};
edge e[maxn];
int first[maxn],len=0;
void buildroad(int x,int y){e[++len]=(edge){y,first[x]};first[x]=len;}
void dfs(int x)
{
	for(int i=first[x];i;i=e[i].next)
	{
		dfs(e[i].y);
		if(!st[x].belong)st[x].belong=st[e[i].y].belong;
		else if(st[x].belong!=st[e[i].y].belong)st[x].belong=-1;
	}
	if(st[x].belong!=-1)ans[st[x].belong]+=st[x].len-st[st[x].link].len;
}

int main()
{
	cin>>T;
	st[0].link=-1;
	for(int j=1;j<=T;j++)
	{
		cin>>s+1;n=strlen(s+1);last=0;
		for(int i=1;i<=n;i++)extend(s[i]-'a',j);
	}
	for(int i=1;i<=id;i++)buildroad(st[i].link,i);
	dfs(0);
	for(int i=1;i<=T;i++)cout<<ans[i]<<'\n';
}

内存天花板，时间破地板