后缀自动机

一个字符串的后缀自动机

一些定义

符号	意义	在$DAG$DAG上的含义
$C$C	原字符串
$trans(S,c)$trans(S,c)	状态转移函数,表示$S$S状态在读入字符$c$c后到达的状态	一条以$S$S为起点,边权为$c$c的边
$trans(S,s)$trans(S,s)	状态转移函数,表示$S$S状态在读入字符串$s$s后到达的状态	一条以$S$S为起点,经过的所有边权依次为$s$s的路径
$right_s\{\}$rights​{}	$s$s在$C$C中所有出现位置末尾的下一个位置
$reg_S\{\}$regS​{}	$right\{\}$right{}相同的所有子串的集合,状态为$S$S
$min_S$minS​	$\min_{S\in reg_S\{\}}\{lenth(s)\}$minS∈regS​{}​{lenth(s)}
$max_S$maxS​	$\max_{S\in reg_S\{\}}\{lenth(s)\}$maxS∈regS​{}​{lenth(s)}
$praent_S$praentS​	$reg_{praent_S}\{\}\subset reg_S\{\}$regpraentS​​{}⊂regS​{}且$reg\{\}$reg{}大小最小	所有$parent$parent构成一颗$parent$parent树

一些性质

$min_s=max_{parent_S}+1$mins​=maxparentS​​+1

一个状态的$right\{\}$right{}是其在$parent$parent树上父节点的$right\{\}$right{}集合的真子集,是其在$parent$parent树上子节点的$right\{\}$right{}的并集

如何构造一个$SAM$SAM

增量算法

考虑已经建出$C[1,i-1]$C[1,i−1]的$SAM$SAM,求$C[1,i]$C[1,i]的$SAM$SAM

设在最后添加的字符$x=C[i]$x=C[i]

考虑状态$S$S,满足$trans(S,x)!=null$trans(S,x)!=null,
即存在一个$r\in right_S\{\}$r∈rightS​{}满足$C[r]=x$C[r]=x,
显然$trans(praent_S,x)!=null$trans(praentS​,x)!=null,即$S$S到$parent$parent树根的所有结点都存在出边$x$x

记录上一个插入的节点$last$last,新建节点$np$np表示当前添加的字符

设$p$p为$last$last到根路径上第一个有出边$x$x的节点,将路径上在$p$p下方的节点都连一条出边$x$x指向$np$np

若初始状态没有出边$x$x,说明$last$last到根路径上的点都不存在出边$x$x,将$parent_np$parentn​p设为初始状态

否则,设$len_S=max_S$lenS​=maxS​,$q=trans(p,x)$q=trans(p,x)

若$len_q=len_p+1$lenq​=lenp​+1,将$parent_{np}$parentnp​设为$q$q

否则,新建状态$nq$nq,$len_{nq}=len_p+1$lennq​=lenp​+1,$trans(nq,*)=trans(q,*)$trans(nq,∗)=trans(q,∗)

将$parent_{nq}$parentnq​设为$parent_{q}$parentq​

再将$parent_{q}$parentq​和$parent_{np}$parentnp​设为$nq$nq

最后将$p$p及其祖先的出边$x$x指向$nq$nq

至于为什么这么做,可以结合样例思考一下

Null

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YgvKLnLI-1598857277428)(https://00ffcc.cf/images/SAM/Null.png)]

a

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-09ajHBGq-1598857277433)(https://00ffcc.cf/images/SAM/a.png)]

ab

aba

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-63l6g6LZ-1598857277445)(https://00ffcc.cf/images/SAM/aba.png)]

abab

ababb

应用

统计子串个数

模板题

#include<bits/stdc++.h>
using namespace std;
#define Ri register
template<typename T>inline T read(Ri T& t)
{Ri T f=1;Ri char ch=getchar();t=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')t=t*10+ch-'0',ch=getchar();t*=f;return t;}
template <typename T,typename...Args>
inline void read(T&t,Args&...args)
{read(t);read(args...);}
int total=1;
int sam[2000006][26];
char S[2000006];
long long cnt[2000006],len[2000006];
int parent[2000006];
int last=1;
void Insert(char c)
{
	int x=c-'a';
	int p=last;
	int np=++total;last=np;
	cnt[np]=1;len[np]=len[p]+1;
	while(sam[p][x]==0&&p)
		sam[p][x]=np,p=parent[p];
	if(p==0)return parent[np]=1,void();
	int q=sam[p][x];
	if(len[q]==len[p]+1)return parent[np]=q,void();
	int nq=++total;
	memcpy(sam[nq],sam[q],sizeof(sam[q]));
	parent[nq]=parent[q];
	parent[q]=parent[np]=nq;
	len[nq]=len[p]+1;
	while(sam[p][x]==q&&p)
		sam[p][x]=nq,p=parent[p];
}
int sum[2000006];//某长度的节点个数 
int main()
{
	scanf("%s",S+1);
	int n=strlen(S+1);
	for(int i=1;i<=n;i++)
		Insert(S[i]);
	for(int i=1;i<=total;i++)
		sum[len[i]]++;
	for(int i=1;i<=total;i++)
		sum[i]+=sum[i-1];
	static int opt[2000006];
	for(int i=1;i<=total;i++)
		opt[sum[len[i]]--]=i;
	long long ans=0;
	for(int i=total;i>=1;i--)
	{
		cnt[parent[opt[i]]]+=cnt[opt[i]];
		if(cnt[opt[i]]>1)
			ans=max(ans,len[opt[i]]*cnt[opt[i]]);
	}
	printf("%lld\n",ans);
	return 0;
}

动态维护本质不同子串个数

link

#include<bits/stdc++.h>
using namespace std;
#define Ri register
template<typename T>inline T read(Ri T& t)
{Ri T f=1;Ri char ch=getchar();t=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9')t=t*10+ch-'0',ch=getchar();t*=f;return t;}
template <typename T,typename...Args>
inline void read(T&t,Args&...args)
{read(t);read(args...);}
map<int,int> sam[200005];
int total=1;
int last=1;
int len[200005];
int parent[200005];
long long ans=0;
inline void Insert(int x)
{
	int np=++total;
	int p=last;last=np;len[np]=len[p]+1;
	while(sam[p].count(x)==0&&p)
		sam[p][x]=np,p=parent[p];
	if(p==0)return parent[np]=1,ans+=len[last]-len[parent[last]],void();
	int q=sam[p][x];
	if(len[q]==len[p]+1)return parent[np]=q,ans+=len[last]-len[parent[last]],void();
	int nq=++total;
	len[nq]=len[p]+1;
	sam[nq]=sam[q];
	parent[nq]=parent[q];
	parent[q]=parent[np]=nq;
	while(p&&sam[p][x]==q)
		sam[p][x]=nq,p=parent[p];
	ans+=len[last]-len[parent[last]];
//	printf("%d %d\n",len[last],len[parent[last]]);
}
int main()
{
	int n;
	read(n);
	while(n--)
	{
		int x;read(x);
		Insert(x);
		printf("%lld\n",ans);
	}
	return 0;
}
nt[last]];
//	printf("%d %d\n",len[last],len[parent[last]]);
}
int main()
{
	int n;
	read(n);
	while(n--)
	{
		int x;read(x);
		Insert(x);
		printf("%lld\n",ans);
	}
	return 0;
}