传送门
其实这道题就是给一个字符串，然后问每一个前缀中有多少个不同的子串。
同样用 \(len\) 数组的性质，如果新加入一个节点 \(x\)，那么它对于整个已加入串新增的不同的子串数量就是 \(len[x]-len[fa[x]]\)。
我试着解释一下为什么，因为 \(fa[x]\) 代表的所有字符串一定就是 \(x\) 的后缀，\(x\) 新增的串长一定大于 \(len[fa[x]]\)，那么 \(x\) 所代表的串中长为 \(len[fa[x]]+1...len[x]\) 的串就是新增的，当然长度唯一嘛，所以新增的数量就是 \(len[x]-len[fa[x]]\)。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e5+10;
int last=1,tot=1,n,fa[N*2],len[N*2];
map<int,int> ch[N*2];
LL ans;
int newnode(int id){fa[++tot]=fa[id];len[tot]=len[id];ch[tot]=ch[id];return tot;}
void insert(int c){
int p=last,np=last=newnode(0);
len[np]=len[p]+1;
for(;p&&!ch[p][c];p=fa[p]) ch[p][c]=np;
if(!p) fa[np]=1;
else{
int q=ch[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else{
int nq=newnode(q);len[nq]=len[p]+1;
fa[q]=fa[np]=nq;
for(;p&&ch[p][c]==q;p=fa[p]) ch[p][c]=nq;
}
}
ans+=len[np]-len[fa[np]];
printf("%lld\n",ans);
}
int main(){
scanf("%d",&n);
for(int i=1,x;i<=n;i++){
scanf("%d",&x);
insert(x);
}
return 0;
}
原文：https://www.cnblogs.com/BakaCirno/p/12670746.html