后缀自动机还是只会打板子，已经知道它是个什么东西了，但还是和它的构造联系不起来。。先背板子吧。
后缀自动机有一个很好的特性就是可以涵盖所有不重复的子串，我们利用这一点在它上面dp就行了；
代码参考：http://blog.csdn.net/fuxey/article/details/51050474
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
const int mod=,maxn=;
char ss[maxn],s[maxn];
int tt[maxn],last,cur=,cnt=,n,len,sum[maxn],ch[maxn][],fa[maxn],dis[maxn];
int c[maxn],q[maxn];
void add(int c,int id){
last=cur;cur=++cnt;
int p=last;dis[cur]=id;
for(;p&&!ch[p][c];p=fa[p])ch[p][c]=cur;
if(!p)fa[cur]=;
else{
int q=ch[p][c];
if(dis[q]==dis[p]+)fa[cur]=q;
else{
int nt=++cnt;dis[nt]=dis[p]+;
memcpy(ch[nt],ch[q],sizeof(ch[]));
fa[nt]=fa[q];fa[q]=fa[cur]=nt;
for(;p&&ch[p][c]==q;p=fa[p])ch[p][c]=nt;
}
}
}
void rsort(){
memset(c,,sizeof(c));
for(int i=;i<=cnt;++i)c[dis[i]]++;
for(int i=;i<=cnt;++i)c[i]+=c[i-];
for(int i=;i<=cnt;++i)q[c[dis[i]]--]=i;
}
int main(){
while(cin>>n){
cnt=;memset(fa,,sizeof(fa));
memset(ch,,sizeof(ch));
for(int i=;i<=n;++i){
scanf("%s",ss+);
cur=;len=strlen(ss+);
for(int j=;j<=len;++j)add(ss[j]-'',j);
}
rsort();//先排一遍序保证计算顺序没有问题，保证一个点在更新别的点之前已经被所有能到它的点更新过；
memset(sum,,sizeof(sum));memset(tt,,sizeof(tt));
sum[]=;tt[]=;
for(int i=,j;i<=cnt;++i){
j=q[i];
for(int k=,t;k<;++k){
if(j==&&(!k))continue;
t=ch[j][k];
(sum[t]+=tt[j]*k+sum[j]*)%=mod;
(tt[t]+=tt[j])%=mod;
//cout<<sum[t]<<' '<<tt[t]<<endl;
}
}
int ans=;
for(int i=;i<=cnt;++i){(ans+=sum[i])%=mod;}
printf("%d\n",ans);
}
//system("pause");
return ;
}
/*
5
101
123
09
000
1234567890
*/
