后缀自动机学习笔记

在后缀家族（后缀树、后缀数组、后缀自动机、后缀平衡树、后缀仙人掌、后缀神域）中，后缀自动机可谓是应用最广的数据结构。

本篇文章基于Menci’s Blog并纠错、拓展与总结。

定义（们）：

后缀自动机（SAM）包含两部分：有向无环单词图（DAWG）和前缀树。
SAM的每一个结点同时存在于这两个结构中。
我们对$S$构造SAM，称$S$是SAM的母串。
记$\left|S\right|$是字符串$S$的长度。

DAWG

DAWG是一个DAG图。
除起始结点外，每个结点代表的含义是能从起始结点到达它的所有子串。
结点间通过转移边相连，每条转移边上有一个字符。
从起始结点沿着转移边走，每条路径对应一个子串。（多条路径可能到达同一个结点）。
SAM可接受所有子串，若要使其仅能接受后缀则可通过打标记解决。

结点

每个结点所表示的所有字符串，一定是母串某个前缀的若干个（不是所有）长度只相差$1$的后缀（前缀+后缀=子串）。
结点$v$所表示的长度最小的子串、最大子串记作$min(v),max(v)$。
结点$v$所表示的最长子串$max(v)$在母串中所有出现的结束位置集合为$end$-$pos(v)$。
有性质：任意两个点的$end$-$pos$集合不同。（否则可合并）

转移边

$u$到$v$有一条字符为$c$的转移边，表示$u$所表示的所有子串加上$c$后得到的子串都可以用$v$表示。
但不一定$v$所表示的所有子串都是由$u$转移而来。

后缀链接与前缀树

$u$的后缀链接指向$v$，当且仅当$\left|min(u)\right|=\left|max(v)\right|+1$且$v$中的所有子串均为$u$中子串的后缀，记为$next(u)=v$。

注意这是定义而不是性质，至于为什么这样定义可以不管。
任意一个结点沿着后缀链接走，最终都会到达DAWG的起始结点，以后缀链接为边，所有结点构成一棵树，即前缀树。DAWG的起始结点即是前缀树的根。

理解

因为后缀自动机初学时难以理解，以上的定义不易深刻理解，因此在将后缀自动机的性质前先引入几个形象的解释。

关于结点

一般我们的结点仅仅表示一个信息，但思考一下如果这样，后缀自动机就需要$O(n^2)$的空间，难以接受。因此我们需要将不必分开的信息合并在一起，故每个结点就代表了多个信息。

每个结点表示的信息不会冲突（比如$end$-$pos$不可能不同），否则需要将它们拆开（这个后面再讲）。
这样的空间量是$O(n)$的，后面再证明。

关于DAWG

DAWG并不是后缀自动机上最重要的结构，它仅仅用有向图表示出所有存在的子串。

关于后缀链接与前缀树的祖先后代关系

每个结点代表了一些串，这些串的部分后缀是相同的。
结点$u$在前缀树上到根的路径构成了所有长度递减后缀公共的串。
其中每个结点$u$包含一些串（$min(u)\rightarrow max(u)$）。
因此到根的路径上包含长度为$[1,\left|max(u)\right|]$的所有子串。

前缀树是后缀自动机最重要的结构，它有重要的性质，后缀自动机的大部分应用都是在前缀树上完成的。

作图

这是一个极为简单的SAM：
母串为$ABC$。

图中的黑色边是转移边，构成DAWG。
图中的红色边是后缀链接，构成前缀树。
图中的蓝色串为每个结点代表的所有子串。
不难发现这样的SAM是仅可接受母串所有子串并满足要求的。

这是一个较为复杂的SAM：
母串为$ABBD$。

不难发现这样的SAM是仅可接受母串所有子串并满足要求的。

暂不用思考其构建方法，我们后面再提到。

性质

性质一

性质二

每个结点$u$包含的所有串的$end$-$pos$均相同。
证明：
这不算一个性质，而算对结点定义中若干个子串的规定。

性质三

在前缀树中，每个结点的$end$-$pos$是其后缀链接的$end$-$pos$的真子集。
证明：
后缀链接所表示的所有串是当前结点表示所有串的后缀，因此其$end$-$pos$一定包含当前结点的$end$-$pos$。
又因为两个结点的$end$-$pos$集合不相等，否则可合并，因此成立。

性质四

后缀自动机的前缀树是原串的反向前缀树。
反向前缀树的定义是：将每个前缀的反串加入trie，并把没有分支的链合并。

那么如果我们将母串的反串建立SAM，它的前缀树即为原串的后缀树。
为了还原后缀树，我们可以求一下每个结点$u$对应的$max(u)$字符串，父子减一下即可得到边上的字符串。

将后缀树Dfs一遍即可得到后缀数组。

这就是后缀树和后缀数组的线性构造方法。

性质五

两个串的最长公共后缀，位于这两个串对应的结点在前缀树上的LCA位置。

理论构建方法

（Menci的博客里有个地方讲错了一点点，这里基本上从Menci博客搬运过来）
我们使用增量算法构造SAM，假设我们已经有了字符串$S$的SAM，只需要考虑如何对其修改得到$S+c$的后缀自动机。
设之前表示整个串的结点为$last$，灰边为转移边，黑边为后缀链接。

现在我们加入新字符$c$，所以$v_1,v_2$添加了新字符$c$后得到的字符串出现了，且他们是新母串的后缀。设它们被点$u$所表示，显然$max(u)=max(v_1)+c,min(u)=max(v_2)+c$。

1.若不存在$v_3$有字符$c$的转移边，则将$next(u)$置为$root$，此时$\left|min(u)\right|=1$。

此时一定有一个异于$v_i$的结点$t$，满足$next(t)=v_3$，且有$t\rightarrow d$的转移边。

此时$d$所代表的串中，既有$t$的子串$+c$得到的串，又含有$t$的后缀$v_3+c$得到的串，它们不全都是$u$的后缀。举个例子：

我们需要将$d$拆成两个点，一个点$n$表示长度小于等于$\left|max(v_3)\right|+1$的子串，用另一个点$o$表示长度更大的子串。

$v_3,v_4$的转移边连向$n$，其余后继连向$o$，$next(n)=next(d),next(o)=n,next(u)=n$。
不难发现这样的拆分满足要求。

实际构建方法

1.建立新结点，令$p=last$，并更新$last$。

1 2	int p=last,u=newnode(Max[last]+1); last=u;

2.沿着前缀树寻找第一个没有该字符儿子的结点。

1	for(; p&&!child[p][data]; p=next[p])child[p][data]=u;

3.情况一：寻找到根节点也无该儿子。

1	if(!p)next[u]=root;

4.情况二：若满足理论构建中的第2种情况。

1 2	int old=child[p][data]; if(Max[old]==Max[p]+1)next[u]=old;

5.情况三：否则即为理论构建中的第3种情况，拆点并更新信息。

int New=newnode(Max[p]+1);
copy(child[old],child[old]+maxc,child[New]);
next[New]=next[old];
next[u]=next[old]=New;
for(; child[p][data]==old; p=next[p])child[p][data]=New;

全部代码

void insert(int data) {
	int p=last,u=newnode(Max[last]+1);
	last=u;
	end_pos[u]=1;
	for(; p&&!child[p][data]; p=next[p])child[p][data]=u;
	if(!p)next[u]=root;
	else {
		int old=child[p][data];
		if(Max[old]==Max[p]+1)next[u]=old;
		else {
			int New=newnode(Max[p]+1);
			copy(child[old],child[old]+maxc,child[New]);
			next[New]=next[old];
			next[u]=next[old]=New;
			for(; child[p][data]==old; p=next[p])child[p][data]=New;
		}
	}
}

复杂度证明

见Menci’s Blog。

大字符集的处理

在字符集大小是常数的时候，后缀自动机时间复杂度是线性的。
如果字符集过大，可以开map存字符，复杂度增加$\log c$。

拓扑序

所以，按照每个结点记录的$max$长度排序，可以同时得到DAWG和前缀树的拓扑序。
使用计数排序可以做到线性的时空复杂度。（对于$max$长度有相同的时候可能会不适用）

void topsort() {
	for(int i=1; i<=cnt; i++)Bucket[Max[i]]++;
	for(int i=1; i<=cnt; i++)Bucket[i]+=Bucket[i-1];
	for(int i=1; i<=cnt; i++)top[Bucket[Max[i]]--]=i;
}

$end$-$pos$集合

初始原串的前缀结点$end$-$pos$为$1$。
先求出拓扑序，沿着逆拓扑序递推即可求出$end$-$pos$集合大小。
若要求出$end$-$pos$集合，需要用到启发式合并Splay。

void get_end_pos() {
	topsort();
	for(int i=cnt; i>=1; i--)end_pos[next[top[i]]]+=end_pos[top[i]];
}

树上的扩展

我们可以把后缀自动机推广到树上的情况。
对于一个结点，我们从它的父亲对应的$last$开始插入新字符，此时有两种实现方法：

每次插入时$last$返回新结点的父亲的$last$，套用以前的插入。（这是正确的，但是因为$\left|max\right|$有重复，故不能计数排序计算拓扑序，只能宽搜）
每次插入时$last$返回新结点的父亲的$last$，将相同的转移合并起来。（时空间效率更高）

需要注意$end$-$pos$的维护，这里给出第二种方法的代码。

void insert(int data) {
	if(child[last][data]) {
		int p=last,old=child[last][data];
		if(Max[old]==Max[p]+1) {
			last=old;
			end_pos[old]++;
		} else {
			int New=newnode(Max[p]+1);
			last=New;
			end_pos[New]=1;
			copy(child[old],child[old]+maxc,child[New]);
			next[New]=next[old];
			next[old]=New;
			for(; child[p][data]==old; p=next[p])child[p][data]=New;
		}
	} else {
		int p=last,u=newnode(Max[last]+1);
		last=u;
		end_pos[u]=1;
		for(; p&&!child[p][data]; p=next[p])child[p][data]=u;
		if(!p)next[u]=root;
		else {
			int old=child[p][data];
			if(Max[old]==Max[p]+1)next[u]=old;
			else {
				int New=newnode(Max[p]+1);
				copy(child[old],child[old]+maxc,child[New]);
				next[New]=next[old];
				next[u]=next[old]=New;
				for(; child[p][data]==old; p=next[p])child[p][data]=New;
			}
		}
	}
}

应用

求两个串的LCS

解法一：

将其中一个串建成后缀自动机，另一个串放在自动机上运行，若匹配则匹配长度$len+1$，若不匹配则根据$max$长度重新计算匹配长度，答案即为匹配长度的最大值。

解法二：

将两个串用分隔符连接建立后缀自动机，将$A$串和$B$串前缀经过的结点分别标注出来，并将标记沿着前缀树传递，统计同时有两种标记的$max$长度即为LCS

求多个串的LCS

将其中一个串建为后缀自动机，其余的串在自动机上运行，记录每次运行每个结点得到的最长串长度，记录所有运行中最长串的最小值，再在最小值中找一个最大的记作答案。
注意每次运行结束更新最小值时需要按照逆拓扑序向后缀连接更新，因为儿子能匹配的祖先一定能匹配，但祖先在更新前不一定是最优答案。

求字符串最小表示

将串扩展一倍建立后缀自动机，从根开始一直沿着最小的转移边转移，转移$|S|$步后停止。

求长度为i的串的最大出现次数

求$k$小子串

参考资料

后缀自动机学习笔记 - Menci’s Blog
后缀自动机及其应用 - 张天扬
Bill Yang后缀自动机笔记初稿