相关知识点可移步 oi-wiki , 相关证明太多实在不想写
下面讲几个经典题目
请你求出 \(S\) 的所有出现次数不为 11 的子串的出现次数乘上该子串长度的最大值。$ |S| \le 10^6$
我们首先需要计算后缀自动机中每个状态 \(v\) 的\(cnt_{v}\) ，使之等于 $ endpos(v) $ 集合的大小。即在字符串中的出现次数。
为了计算这些值，我们进行以下操作。对于每个状态 \(v\) ，如果它不是通过复制创建的（且它不是初始状态 ），我们将它的 \(cnt_{v}\) 初始化为 1。然后我们按它们的长度 \(len\) 降序遍历所有状态，并将当前的 \(cnt_{v}\) 的值加到后缀链接指向的状态上，即：\(cnt_{link(v)} + = cnt_{v}\)
为什么可以这么做呢？\(cnt_{link(v)} + = cnt_{v}\) 的含义就是如果有一个字符串 \(v\) 出现了 \(cnt_{v}\) 次，那么它的所有后缀也在完全相同的地方结束，即也出现了 \(cnt_{v}\) 次。重复计数的问题，因为我们只将一个状态的位置添加到 一个 其它的状态上，所以一个状态不可能以两种不同的方式将其位置重复地指向另一个状态。
知道 \(cnt\) 数组后，对于 \(cnt_v > 1\) 的点，我们求出 \(max(cnt_v \times len_v)\) 即可。
排序可以使用桶排
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int read()
{
int k=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
}
const int N=2000055;
int n,m,ch[N][26],a[N],c[N];
int last,tot,link[N],len[N],size[N];
char s[N];
void init()
{
last=tot=0;len[0]=0;link[0]=-1;
}
void extend(int c)
{
int cur=++tot,p=last;len[cur]=len[last]+1;size[cur]=1;
for(;p!=-1&&!ch[p][c];p=link[p]) ch[p][c]=cur;
if(p==-1) link[cur]=0;
else
{
int q=ch[p][c];
if(len[p]+1==len[q]) link[cur]=q;
else
{
int clone=++tot;
len[clone]=len[p]+1;
link[clone]=link[q];
memcpy(ch[clone],ch[q],sizeof(ch[q]));
for(;p!=-1&&ch[p][c]==q;p=link[p])
ch[p][c]=clone;
link[q]=clone;link[cur]=clone;
}
}
last=cur;
}
int main()
{
scanf("%s",s);
n=strlen(s);
init();
for(int i=0;i<n;i++)
extend(s[i]-'a');
for(int i=1;i<=tot;i++)
c[len[i]]++;
for(int i=1;i<=tot;i++)
c[i]+=c[i-1];
for(int i=1;i<=tot;i++)
a[c[len[i]]--]=i;
ll ans=0;
for(int i=tot;i>=1;i--)
{
size[link[a[i]]]+=size[a[i]];
if(size[a[i]]>1)
ans=max(ans,1ll*size[a[i]]*len[a[i]]);
}
printf("%lld\n",ans);
return 0;
}给一个字符串，求每一个前缀有多少个不同的子串
$ |S| \leq 10^5 $ ,字符集大小 \(10^9\)
后缀自动机中每个节点对应的字符串数是 $ len_{i} - len_{link(i)} $ ,每次插入字符的时候跟新答案即可，记住要用 map 来存储转移。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#define ll long long
using namespace std;
int read()
{
int k=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
}
const int N=500055;
int n,m,a[N],c[N];
int last,tot,link[N],len[N],size[N];
char s[N];
ll ans;
map<int,int> ch[N];
void init()
{
last=tot=0;len[0]=0;link[0]=-1;
}
void extend(int c)
{
int cur=++tot,p=last;len[cur]=len[last]+1;
for(;p!=-1&&!ch[p][c];p=link[p]) ch[p][c]=cur;
if(p==-1) link[cur]=0;
else
{
int q=ch[p][c];
if(len[p]+1==len[q]) link[cur]=q;
else
{
int clone=++tot;
len[clone]=len[p]+1;
link[clone]=link[q];
ch[clone]=ch[q];
for(;p!=-1&&ch[p][c]==q;p=link[p])
ch[p][c]=clone;
link[q]=clone;link[cur]=clone;
}
}
last=cur;
ans+=len[cur]-len[link[cur]];
}
int main()
{
n=read();init();
for(int i=1;i<=n;i++)
{
int x=read();
extend(x);
printf("%lld\n",ans);
}
return 0;
}求两个字符串 \(S,T\) 的最长公共字串的长度。 $ |S| \leq 2.5 \times 10^5 ,|T| \leq 2.5 \times 10^5$
先构造出 \(S\) 的后缀自动机，我们记录一个 \(l\) 来表示当前匹配长度，\(now\) 表示当前在自动机上的节点，开始 $ now=0 ,l=0 $ ，我们依次添加字符 \(T_i\) ，如果 \(now\) 有到 \(T_i\) 的转移，我们就把 \(l++\)，并且让 \(now\) 转移。否则我们就要缩短当前串的长度继续匹配，即 $ now= link(now) , l=len(now) $ ,直到存在转移为止。每次匹配完记录最大的 \(l\) 即可。
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define ll long long
using namespace std;
int read()
{
int k=0,f=1;char c=getchar();
for(;!isdigit(c);c=getchar()) if(c=='-') f=-1;
for(;isdigit(c);c=getchar()) k=k*10+c-'0';return k*f;
}
const int N=500055;
int n,m,ch[N][26],a[N],c[N];
int last,tot,link[N],len[N],size[N];
char s[N],t[N];
void init()
{
last=tot=0;len[0]=0;link[0]=-1;
}
void extend(int c)
{
int cur=++tot,p=last;len[cur]=len[last]+1;size[cur]=1;
for(;p!=-1&&!ch[p][c];p=link[p]) ch[p][c]=cur;
if(p==-1) link[cur]=0;
else
{
int q=ch[p][c];
if(len[p]+1==len[q]) link[cur]=q;
else
{
int clone=++tot;
len[clone]=len[p]+1;
link[clone]=link[q];
memcpy(ch[clone],ch[q],sizeof(ch[q]));
for(;p!=-1&&ch[p][c]==q;p=link[p])
ch[p][c]=clone;
link[q]=clone;link[cur]=clone;
}
}
last=cur;
}
int main()
{
scanf("%s",s);
n=strlen(s);
init();
for(int i=0;i<n;i++)
extend(s[i]-'a');
scanf("%s",t);
m=strlen(t);
int now=0,ans=0,l=0;
for(int i=0;i<m;i++)
{
int x=t[i]-'a';
while(now&&!ch[now][x]) now=link[now],l=len[now];
if(ch[now][x]) now=ch[now][x],l++;
if(l>ans) ans=l;
}
printf("%d\n",ans);
return 0;
}原文：https://www.cnblogs.com/waing/p/12196391.html