C++14(g++5.4) 解法, 执行用时: 28ms, 内存消耗: 18660K, 提交时间: 2020-09-01 13:33:38

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int M=1e5+9;
const int MX=1e6+9;
string s[M];
int n,last,vis[MX];
struct Sam{
    int tran[MX][26],fa[MX],maxlen[MX],endpos[MX];
    int tot=1;
    int insert(int a,int last){
        if( tran[last][a] ){
            int p=last,x=tran[last][a];
            if( maxlen[x]==maxlen[p]+1)  return x;
            else{
                int y=++tot;
                maxlen[y]=maxlen[p]+1;
                fa[y]=fa[x];fa[x]=y;
                for( int i=0 ; i<26 ; i++ ) tran[y][i]=tran[x][i];
                while( p && tran[p][a]==x ) tran[p][a]=y,p=fa[p];
                return y;
            }
        }
        int p=last,z=++tot;
        maxlen[z]=maxlen[p]+1;
        endpos[z]=1;
        while( p && !tran[p][a] ) tran[p][a]=z,p=fa[p];
        if( !p ) fa[z]=1;
        else{
            int q=tran[p][a];
            if( maxlen[q]==maxlen[p]+1 ) fa[z]=q;
            else{
                int y=++tot;
                maxlen[y]=maxlen[p]+1;
                fa[y]=fa[q],fa[q]=fa[z]=y;
                for( int i=0 ; i<26 ; i++ ) tran[y][i]=tran[q][i];
                while( q && tran[p][a]==q ) tran[p][a]=y,p=fa[p];
            }
        }
        return z;
    }
    int vis[MX];
    ll ans[MX];

    void solve(){
        for( int i=1 ; i<=n ; i++ ){
            int pos=1;
            for( int j=0 ; j<s[i].size() ; j++ ){
                pos=tran[pos][s[i][j]-'a'];
                int p=pos;
                while( p && vis[p]!=-1 && vis[p]!=i ){
                    if( !vis[p] ) vis[p]=i;
                    else vis[p]=-1;
                    p=fa[p];
                }
            }
        }
        for( int i=2 ; i<=tot ; i++ ){
            if( vis[i] && vis[i]!=-1 )
                ans[vis[i]]+=maxlen[i]-maxlen[fa[i]];
        }
        for( int i=1 ; i<=n ; i++ ) printf("%lld\n",ans[i]);
        return ;
    }
}sam;


int main()
{
//    freopen("input.txt","r",stdin);
    scanf("%d",&n);
    for( int i=1 ; i<=n ; i++ ){
        cin >> s[i] ;
        last=1;
        for( int j=0 ; j<s[i].size() ; j++  )
            last=sam.insert(s[i][j]-'a',last);
    }
    sam.solve();

    return 0;
}

C++(clang++11) 解法, 执行用时: 23ms, 内存消耗: 15620K, 提交时间: 2021-02-11 19:45:42

#include<bits/stdc++.h>
using namespace std;
void read(int &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	for(;!isdigit(ch);ch=getchar())
	if(ch=='-')
	f=-f;
	for(;isdigit(ch);ch=getchar())
	x=x*10+ch-'0';
	x*=f;
}
void print(int x)
{
	if(x<0)
	putchar('-'),x=-x;
	if(!x)
	return;
	print(x/10),putchar(x%10+48);
}
void write(int x)
{
	if(!x)
	putchar('0');
	else
	print(x);
	putchar('\n');
}
const int maxn=3e5+10;
char ss[maxn],s[maxn];
int n,qs=1,cnt=1,lstp=1,tot;
int tr[maxn][27],par[maxn],ml[maxn],vis[maxn],len[maxn],ans[maxn];
void append(int x)
{
	int p=lstp,np=++cnt;
	lstp=np,ml[np]=ml[p]+1;
	for(;p&&tr[p][x]==0;p=par[p])
	tr[p][x]=np;
	if(p==0)
	return par[np]=qs,void();
	int q=tr[p][x];
	if(ml[p]+1<ml[q])
	{
		int nq=++cnt;
		ml[nq]=ml[p]+1;
		memcpy(tr[nq],tr[q],sizeof(tr[nq]));
		par[nq]=par[q],par[q]=par[np]=nq;
		for(;p&&tr[p][x]==q;p=par[p])
		tr[p][x]=nq;
	}
	else
	par[np]=q;
}
int main()
{
	read(n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",ss+1);
		len[i]=strlen(ss+1);
		lstp=qs;
		for(int j=1;j<=len[i];j++)
		s[++tot]=ss[j],append(ss[j]-'a'+1);
	}
	tot=0;
	for(int p,i=1;i<=n;i++)
	for(int now=qs,j=1;j<=len[i];j++)
	{
		now=tr[now][s[++tot]-'a'+1];
		for(p=now;p&&vis[p]!=-1&&vis[p]!=i;p=par[p])
		if(vis[p]!=0)
		vis[p]=-1;
		else
		vis[p]=i;
	}
	for(int i=1;i<=cnt;i++)
	if(vis[i]!=-1)
	ans[vis[i]]+=ml[i]-ml[par[i]];
	for(int i=1;i<=n;i++)
	write(ans[i]);
	return 0; 
}