题解

把所有字符串用不同的分隔符拼接成一个大串，并记录每个后缀属于哪头牛。所有分隔符都大于 'z'，因此不会与原串的字符混淆。对大串建立后缀数组及 height（LCP） 数组，再用 ST 表维护区间 LCP 的最小值，便可以在 O(1) 时间求出任意两个后缀的最长公共前缀长度。

单独来看某头牛的名字，若长度为 len，它一共有 len(len+1)/2 个子串。为了得到“不同因子”，只需扣掉那些与其他字符串有公共前缀的子串长度。设 sa[i] 的后缀属于字符串 id，我们找到与它相邻且属于不同字符串的后缀，取两者的 LCP 作为这条后缀被别人“覆盖”的最大长度。更精确地，为了找出真正的最大 LCP，我们需要定位到左边最近、右边最近属于其它字符串的后缀，通过 RMQ 求得与它们的 LCP，再取最大值。该长度即为从当前后缀延伸出的、不能算作“独有”的子串数量。

把每个后缀贡献的长度按所属字符串累加，就可以得到每头牛需要扣掉的数量，差值便是答案。由于后缀数组与 RMQ 的构建都是线性的，整个算法的时间复杂度为 O(|S| log |S|)，其中 |S| 是所有字符串长度之和。

#include <bits/stdc++.h>
#define N 500001
using namespace std;
int n;
int a[N];long long ans[N];
int sa[N],rk[N],oldrk[N],he[N];
int cnt[N],id[N],st[N][30];
int pos[N];
char tmp[N];
int s[N];
void getsa(){
	int m=400000;
	for (int i=1;i<=n;i++)cnt[rk[i]=s[i]]++;
	for (int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
	for (int i=n;i;i--)sa[cnt[rk[i]]--]=i;
	for (int w=1,p=0;;w<<=1,m=p,p=0){
		for (int i=n-w+1;i<=n;i++)id[++p]=i;
		for (int i=1;i<=n;i++)if (sa[i]>w)id[++p]=sa[i]-w;
		memset(cnt,0,sizeof cnt);
		for (int i=1;i<=n;i++)cnt[rk[i]]++;
		for (int i=1;i<=m;i++)cnt[i]+=cnt[i-1];
		for (int i=n;i;i--)sa[cnt[rk[id[i]]]--]=id[i];
		p=0;
		memcpy(oldrk,rk,sizeof rk);
		for (int i=1;i<=n;i++){
			if (oldrk[sa[i]]==oldrk[sa[i-1]]&&oldrk[sa[i]+w]==oldrk[sa[i-1]+w]){
				rk[sa[i]]=p;
			}else{
				rk[sa[i]]=++p;
			}
		}
		if (p==n)break;
	}
}
void gethe(){
	for (int i=1,k=0;i<=n;i++){
		if (!rk[i])continue;
		if (k)k--;
		while (s[i+k]==s[sa[rk[i]-1]+k])++k;
		he[rk[i]]=k;
	}
}
int query(int l,int r){
	l++;
	int k=log2(r-l+1);
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
signed main(){
	cin>>n;
	int tmpn=0;
	for (int i=1;i<=n;i++){
		scanf("%s",tmp+1);
		int len=1;
		for (;tmp[len];len++){
			s[++tmpn]=tmp[len];
			pos[tmpn]=i;
		}
		len--;
		s[++tmpn]='z'+i;
		ans[i]=1ll*len*(len+1)/2;
	}
	s[tmpn--]=0;
	swap(n,tmpn);
	getsa();
	gethe();
	for (int i=1;i<=n;i++)st[i][0]=he[i];
	for (int j=1;(1<<j)<=n;j++){
		for (int i=1;i+(1<<j)-1<=n;i++){
			st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
		}
	}
	int lst=0,last=0;
	for (int i=n;i;i--){
		if (pos[sa[i]]!=pos[sa[last]]){
			lst=last;
		}
		last=i;
		a[i]=(lst<=i?0:query(i,lst));
	}
	for (int i=1;i<=n;i++){
		ans[pos[sa[i]]]-=max(a[i],he[i]);
	}
	for (int i=1;i<=tmpn;i++){
		cout<<ans[i]<<endl;
	}
	return 0;
}