rt

我自己真广义 SAM 还挂了一些点

#include<bits/stdc++.h>
#define fo(i,a,b) for(I i(a),_ed(b);i<=_ed;++i)
using namespace std;using I=int;using LL=long long;using V=void;
const I N=2e5+10;
LL ans[N];
namespace SAM{
	I las=1,cnt=1,tr[N][26],fa[N],len[N],fg[N];
	V operate(I p,I q,I id,I c){
		++cnt;copy(tr[q],tr[q]+26,tr[cnt]);
		fa[cnt]=fa[q];fa[q]=cnt;fg[cnt]=id;len[cnt]=len[p]+1;
		for(;tr[p][c]==q;p=fa[p])tr[p][c]=cnt;}
	V ins(I c,I id,I p=las){
		if(I q=tr[p][c]){
			if(len[q]==len[p]+1)
				las=q,fg[q]=-1;
			else operate(p,q,id,c),las=cnt;
			//删掉这一行就能 AC 
			return;
		}
		len[las=++cnt]=len[p]+1;
		if(fg[cnt])fg[cnt]=-1;
		else fg[cnt]=id;
		for(;p&&!tr[p][c];p=fa[p])tr[p][c]=cnt;
		if(!p)return fa[las]=1,V();
		I q=tr[p][c];
		if(len[q]==len[p]+1)return fa[las]=q,V();
		operate(p,q,id,c);
		fa[las]=cnt;}
	V insert(string&s,I id){las=1;
		for(I i:s)ins(i-'a',id);}
	V genans(){I t[cnt+1]={},a[cnt+1]={};
		fo(i,1,cnt)++t[len[i]];
		fo(i,1,cnt)t[i]+=t[i-1];
		fo(i,1,cnt)a[t[len[i]]--]=i;
		fo(i,1,cnt){I x=a[cnt-i+1];
			if(~fg[x])ans[fg[x]]+=len[x]-len[fa[x]];
			if(fg[fa[x]]==0)fg[fa[x]]=fg[x];
			else if(fg[fa[x]]^fg[x])fg[fa[x]]=-1;}
	}
}
I n;string s;
I main(){ios::sync_with_stdio(0);cin.tie(0);
	cin>>n;
	fo(i,1,n)cin>>s,SAM::insert(s,i);
	SAM::genans();
	fo(i,1,n)printf("%lld\n",ans[i]);
	return 0;}