后缀自动机相关

文章目录

写在前面
后缀自动机的图的理解
构建自动机
- 约定
$right$集合
- 求$right$集合的大小
- $right$集合的理解
后缀自动机的应用

写在前面

本篇博客主要讲一些自己的理解，不喜勿喷
发现网上的博客关于 $r i g h t$ 集合只讲了如何做，没有讲清原因，于是和同学讨论了很久之后记录一下
如有没有看懂的地方或者错误的地方，欢迎提问或者指出
如有其它疑问也可提出，博主也会进行解答
本博客内容为对各种方法的理解与深入分析，所以有点部分会长了一点点
若只想知道方法，可跳过中间的思考

后缀自动机的图的理解

$P a r e n t$ 树上的节点与后缀自动机的节点完全一样，但是边 不一样
从 根节点出发，能走出所有的子串，并只能走出子串
$e n d p o s$ 是一个集合，表示一个串出现的所有位置，以最后一个字符所在位置为出现位置
$r i g h t$ 集合表示 $e n d p o s$ 相同的子串的集合，一个 $r i g h t$ 集合可以表示多个子串，这些子串的长度一定是连续的，并且有后缀关系， $r i g h t$ 的大小表示的就是其所表示的 $e n d p o s$ 集合的大小，即该 $e n d p o s$ 集合有多少元素
两个 $r i g h t$ 的关系只有两种，要么是包含关系，要么互相独立，不会有交集

若两个串有相同的 $e n d p o s$ ，那么必有一个为另一个的子串
一个 $r i g h t$ 集合 $r 1$ 可以被另一个 $r i g h t$ 集合 $r 2$ 包含，此时一定满足 $r 2$ 是 $r 1$ 的后缀
根据2.，我们可以在后缀自动机上从根节点开始跑，可以跑出所有子串，跑到某个点时，此时该点的 $r i g h t$ 的大小，亦表示当前匹配到的这个字符串 出现次数
$P a r e n t$ 树可由后缀自动机建出来，每个节点的 $f a i l$ 节点所表示出的字符串一定是其后缀，因为 $f a i l$ 节点的 $r i g h t$ 集合包含该节点。

为什么？因为后缀自动机就是要建出这样的树怎么建出来可去看其它dalao的详细讲解，本文只会讲关键意义
自动机节点的后缀表示的是以该节点为末尾的后缀

构建自动机

事先申明，本人打的是数组版

约定

$\begin{matrix} <mstyle displaystyle="true" scriptlevel="0"> </mstyle> & <mstyle displaystyle="true" scriptlevel="0"> f a \to f a i l </mstyle> \\ <mstyle displaystyle="true" scriptlevel="0"> </mstyle> & <mstyle displaystyle="true" scriptlevel="0"> l e n \to l o n g e s t <mtext> </mtext> l e n g t h </mstyle> \\ <mstyle displaystyle="true" scriptlevel="0"> </mstyle> & <mstyle displaystyle="true" scriptlevel="0"> s i z e \to s i z e <mtext> </mtext> o f <mtext> </mtext> r i g h t </mstyle> \end{matrix}$
主串为原串的前缀，旧主串为上一个前缀加入自动机后是哪个节点
另外， $s i z e$ 不影响构建后缀自动机，可以忽视，本文会在后面讲 $P a r e n t$ 时讲 $s i z e$
主要内容写在代码里，会重复上面的内容以便理解

#include <cstdio>
#include <cstring>
const int maxn = 2000006;
const int maxc = 27;
int tot=1,last=1;//last -> 旧主串的节点
int fa[maxn],len[maxn],size[maxn];
//fa -> fail fa[x]的right集合一定包含x的right集合 fa[x]一定是x的后缀
//len[x] -> x为后缀最长串长度
//size[x] -> x 号节点表示的right集合的大小
int son[maxn][maxc];//son[p][c] -> 在p所代表的集合后加c字符，该字符c是哪个节点 亦可认为是边

//1 号节点为初始节点 初始节点没有fa

//{{{构建SAM
void extend (int c)
{
	int p=last,np=++tot;
	last=tot,len[np]=len[p]+1;
	while (p&&!son[p][c])	son[p][c]=np,p=fa[p];//跳后缀 因为是旧主串的后缀 它们全都可以加一个c
	//当前p没有c，表示该子串是第一次出现，p向np连一条c边
	//若当前p有c了表示后面的fa所表示的后缀有节点集合表示了以c为结尾的后缀了(因为曾经出现过)，此时出现了两个以c结尾的right集合
	if (!p)	fa[np]=1;//表示c从未出现过 它的后缀为空
	else{
		//要处理这两个以c为末尾的节点
		int q=son[p][c];
		if (len[q]==len[p]+1)	fa[np]=q;//q是新主串的后缀
		else{
			//即len[q]>len[p]+1
			int nq=++tot;//不是新主串的后缀 因为p是新主串的后缀 而len[q]>len[p]+1且q还没被跳过（若是其后缀，按理说应该先被跳到
			len[nq]=len[p]+1;//p的endpos多了个n 所以要新节点 表示由p+c得到的后缀 即nq 
			fa[nq]=fa[q];//nq只是endpos变多 其样子仍是原来那样 其后缀仍是原来的后缀
			fa[np]=fa[q]=nq;//nq 是 q的后缀 也是新主串的后缀
			memcpy(son[nq],son[q],sizeof(son[q]));
			while (son[p][c]==q)	son[p][c]=nq,p=fa[p];//p的后缀的endpos也多了个n 
		}
	}
	size[np]=1;//该节点right大小初值赋值为1
}
//}}}

$r i g h t$ 集合

求 $r i g h t$ 集合的大小

我们知道， $r i g h t$ 在 $P a r e n t$ 树上是有各种包含关系
所以要在 $P a r e n t$ 上求 $r i g h t$ 集合大小
先将主串的 $r i g h t$ 集合的大小赋初值为1,该过程在构建后缀自动机时完成
一个 $r i g h t$ 集合的大小即为其儿子 $r i g h t$ 集合的大小的和加上其原本的大小(可能为1)

$r i g h t$ 集合没有交集，主串节点的 $r i g h t$ 集合的大小就是1

只有主串表示的点能是叶子节点，但是叶子节点的 $r i g h t$ 集合不仅仅表示主串上的点，且主串上的点不一定是叶子节点
为什么
两种理解

$P a r e n t$ 树上的边是由 $f a [i]$ 连向 $i$
新开出来的辅助节点都是别人的 $f a$ ，那么其一定不会是叶子节点
考虑任意一个子串，若其只出现一次，那么以该子串为末尾的主串(前缀)一定比它长，(它是该主串的后缀)，该节点一定是主串节点
所以在构建自动机时只需将主串的 $s i z e$ 赋初值为1
那么，一个主串可以重复出现，则其就有儿子了，为什么仍然给其赋初值为1呢
- 对于字符串 $a b a c$ ，我们画一下 $P a r e n t$ 树
  
  会发现，将一个 $r i g h t$ 集合分成小 $r i g h t$ 集合时，有元素丢失了(2号节点到4号节点)
  这种情况为第一个字符在后面出现过的情况
  考虑任意一个靠后的点的 $e n d p o s$ 集合，它的后缀的 $e n d p o s$ 集合一定被其包含，若 $e n d p o s$ 元素个数为1，那就是主串节点，不为1，则一定有儿子 $e n d p o s$ 元素比它少
  只有最前面的这一个字符是没有后缀的，它的儿子中是没有 $1$ 这个集合的，也就是说少了1个元素，所以其赋初值为1没有问题
- 将上面的情况扩展，若有主串重复出现(即一个前缀在中间出现了),如 $a b c a b$
  不算第一个字符的那种情况， $a b$ 的 $r i g h t$ 集合的儿子里又丢失了 $2$
  上面的情况是因为其没有后缀，而该种情况则为，其后缀的 $r i g h t$ 集合要么是它的父亲，要么和它相同
  于是就丢失了它第一次出现的位置

所以给主串赋初值为1是正确且必须的

所以我们要做的就是，先建出 $P a r e n t$ 树，然后在上面跑一次 $d f s$
当然，我们也可以直接递推，因为是 $D A G$ ，所以可以拓扑的去计算，即由儿子算父亲，长度越大自然在 $P a r e n t$ 树上就处于越下面的位置，所以按照长度从大到小排序，这一步可以选择 $s o r t$ ，也可以基数排序
$C o d e$

for (int i=2;i<=tot;++i)	add(fa[i],i);//因为根节点没有fa，所以要从2开始枚举，当然也可以设根节点为0，那么还得给根节点的fa赋初值为-1，上面特判也得改一下
dfs(1);

void dfs (int p)
{
	for (int e=head[p];e;e=nxt[e]){
		dfs(to[e]);
		size[p]+=size[to[e]];
	}
}

//基数排序 常数较小
for (int i=1;i<=tot;++i)	++cup[len[i]];
for (int i=1;i<=n;++i)		cup[i]+=cup[i-1];
for (int i=1;i<=tot;++i)	mp[cup[len[i]]--]=i;
for (int i=1;i<=tot;++i)	size[fa[i]]+=size[i];

$r i g h t$ 集合的理解

$r i g h t$ 集合个人认为很神奇
我们会发现， $r i g h t$ 集合的大小仅由主串节点更新，遇到主串节点时其 $s i z e$ 就会加1
换句话说，一个节点 $r i g h t$ 集合的大小等于其子树(包括它自己)中，有多少个节点是主串节点
这句话该怎么理解

一个子串一定是一个主串(前缀)的后缀
每个主串(前缀)不相同

那么 一个节点的 $r i g h t$ 集合大小等于该串是多少个前缀的后缀

所以，在 $P a r e n t$ 树上一个节点的 $r i g h t$ 集合的大小亦可表示为
$e n d p o s$ 为该 $r i g h t$ 集合所对应的 $e n d p o s$ 集合的串是多少个前缀的后缀
亦可表示该子树中有多少个主串节点

后缀自动机的应用

判断是否是子串

根据2.

从 根节点出发，能走出所有的子串，并只能走出子串

在后缀自动机上从根节点出发跑一遍即可
~~Trie树又被吊打了~~

不同子串个数

这个有两种方式

我们知道可能有多个字符串共用一个 $r i g h t$ ，这些串的长度肯定不一样，一样就是相同串了，那么我们用 $l e n [i] - l e n [f a [i]]$ 即可得出该 $r i g h t$ 集合是几个串共用的，对每个结点都这么求一次，总数便是不同子串个数
即要求 $\sum_{i = 1}^{t o t} (l e n [i] - l e n [f a [i]])$
考虑 $D P$ ，根据上面 2. ，我们可以从根节点出发，把整个后缀自动机都跑一边，每遇到一个结点就给答案加一

若该不同子串有这样的定义
位置不同的相同子串算不同子串
我们就可考虑7.

根据2.，我们可以在后缀自动机上从根节点开始跑，可以跑出所有子串，跑到某个点时，此时该点的 $r i g h t$ 的大小，亦表示当前匹配到的这个字符串 出现次数

先求出每个 $r i g h t$ 的大小，每遇到一个结点给答案加 $s i z e$ 即可

第K小子串

把从该节点出发还有多少子串记录下来，然后向 $S p l a y$ 那样跑即可

ll dfs (int x)//先处理出还有多少子串
{
	if (num[x]!=-1)	return num[x];
	num[x]=size[x];
	for (int i=1;i<=26;++i)
		if (son[x][i])	num[x]+=dfs(son[x][i]);
	return num[x];
}

void kth (int x,ll k)//求第k小
{
	if (k<=size[x])	return;
	k-=size[x];
	for (int i=1;i<=26;++i){
		if (son[x][i]){
			if (k<=num[son[x][i]]){
				printf("%c",i+'a'-1);
				kth(son[x][i],k);
				return;
			}
			else	k-=num[son[x][i]];
		}
	}
}