后缀自动机的原理就不在赘述了，这里主要介绍它的应用。
板子：
struct node{
int c[26],len,fa;
} a[maxn];
void build(int x){
int p=las;int np=las=++tot;
a[np].len=a[p].len+1;
for(;p&&!a[p].c[x];p=a[p].fa)
a[p].c[x]=np;
if(!p)
a[np].fa=1;
else{
int q=a[p].c[x];
if(a[q].len==a[p].len+1)
a[np].fa=q;//don't write 'a[p].fa=q'!
else{
int nq=++tot;
a[nq]=a[q];
a[nq].len=a[p].len+1;//don't forget!
a[q].fa=a[np].fa=nq;
for(;p&&a[p].c[x]==q;p=a[p].fa)
a[p].c[x]=nq;
}
}
siz[np]=1;
}
一、统计子串出现次数
一个子串的出现次数为它在母树中的儿子的数量，在母树上 \(dfs\) 即可。
\(code:\)
for(int i=0;i<s.size();++i)
build(s[i]-'a');
for(int i=1;i<=tot;++i)
++c[a[i].len];
for(int i=1;i<=tot;++i)
c[i]+=c[i-1];
for(int i=1;i<=tot;++i)
id[c[a[i].len]--]=i;
for(int i=tot;i>=1;--i){
int p=id[i];
siz[a[p].fa]+=siz[p];
if(siz[p]>1)
ans=max(ans,1ll*siz[p]*a[p].len);
}
printf("%lld\n",ans);
return 0;
例题：P5341 [TJOI2019] 甲苯先生和大中锋的字符串
\(code:\)
void work(){
tot=las=1;ans=0;
cin>>s;scanf("%d",&n);
for(int i=0;i<s.size();++i)
build(s[i]-'a');
for(int i=1;i<=tot;++i)
++c[a[i].len];
for(int i=1;i<=tot;++i)
c[i]+=c[i-1];
for(int i=1;i<=tot;++i)
id[c[a[i].len]--]=i;
for(int i=tot;i>=1;--i){
int p=id[i];
siz[a[p].fa]+=siz[p];
if(siz[p]==n)//差分思想，令f[i]表示出现次数为n，长度为i的字符串个数，则sum[i]=f[i]-f[i+1]
++sum[a[p].len],--sum[a[a[p].fa].len];
}
for(int i=s.size();i>=1;--i){
sum[i]+=sum[i+1];//得到上述的f[i]
if(sum[ans]<sum[i])
ans=i;
}
if(ans)
printf("%d\n",ans);
else
printf("-1\n");
for(int i=0;i<=tot;++i){
c[i]=sum[i]=0;
siz[i]=id[i]=a[i].fa=a[i].len=0;
for(int j=0;j<26;++j)
a[i].c[j]=0;
}
}
二、统计不同子串个数
后缀自动机有一个性质：从根节点开始跑，每一条路径代表一个子串。
又因为后缀自动机是个 \(DAG\) ，所以在后缀自动机上跑 \(DP\) 即可。
例题：P2408 不同子串个数
\(code:\)
signed main(){
scanf("%lld",&n);
cin>>s;
len=s.size();
for(int i=0;i<len;++i)
add(s[i]-'a');
for(int i=1;i<=tot;++i)
++cnt[a[i].len];
for(int i=1;i<=len;++i)
cnt[i]+=cnt[i-1];
for(int i=1;i<=tot;++i)
d[cnt[a[i].len]--]=i;
for(int i=tot;i>=1;--i)
siz[a[d[i]].fa]+=siz[d[i]];
for(int i=1;i<=tot;++i)
sum[i]=siz[i]=1;
sum[1]=siz[1]=0;
for(int i=tot;i>=1;--i)
for(int j=0;j<26;++j)
sum[d[i]]+=sum[a[d[i]].ch[j]];
printf("%lld\n",sum[1]);
return 0;
}
三、字典序第 \(K\) 小子串
令 \(siz[i]\) 表示 \(i\) 所代表的 \(Endpos\) 的集合大小，也就是 \(i\) 所对应字符串集合的出现次数
\(T=0\) 时，本质相同的子串在不同位置出现算相同，所以 \(siz[i]=1\) ，即将每个字符串集合的 \(Endpos\) 集合大小（字符串集合元素出现次数）置为1
\(T=1\) 时，本质相同的子串在不同位置出现算不同，那么累加后的 \(siz\) 表示实际上 \(Endpos\) 的集合大小
void dfs(int p,int k){
if(k<=siz[p])
return ;
k-=siz[p];
for(int i=0;i<26;++i){
int to=a[p].ch[i];
if(!to)
continue;
if(k>sum[to])
k-=sum[to];
else{
printf("%c",i+'a'),dfs(to,k);
return ;
}
}
}
int main(){
cin>>s;
scanf("%d%d",&t,&k);
len=s.size();
for(int i=0;i<len;++i)
add(s[i]-'a');
for(int i=1;i<=tot;++i)
++cnt[a[i].len];
for(int i=1;i<=len;++i)
cnt[i]+=cnt[i-1];
for(int i=1;i<=tot;++i)
d[cnt[a[i].len]--]=i;
for(int i=tot;i>=1;--i)
siz[a[d[i]].fa]+=siz[d[i]];
for(int i=1;i<=tot;++i)
if(t==0)
sum[i]=siz[i]=1;
else
sum[i]=siz[i];
sum[1]=siz[1]=0;
for(int i=tot;i>=1;--i)
for(int j=0;j<26;++j)
sum[d[i]]+=sum[a[d[i]].ch[j]];
if(sum[1]>=k)
dfs(1,k);
else
printf("-1\n");
return 0;
}