后缀自动机

后缀自动机(Suffix Automaton, SAM)

Endpos Set

对于给定的一个字符串，如何构造一个状态转移图使之恰好包含其所有子串？一个显然的做法是，把这个字符串的所有后缀插入到一棵前缀树中。这是正确的状态转移图（自动机），但不是最小的自动机。1983年人们提出了后缀自动机，可以被证明是能够表示给定字符串的所有子串的最小自动机。

在后缀自动机中，人们提出了用endpos集合作为自动机状态的方法。我们把一个子串$w$在原串$s$中的右端点坐标集合称为$w$在$s$中的endpos set，简称endset。例如$s$=ababc，$w$=ab时，$w$的endset就是$\{2,4\}$，$w$=b时endset也是$\{2,4\}$，$w$=bab时endset是$\{4\}$。一个子串只对应一个endset，而一个endset可能对应着不止一个子串。例如上例中endset$\{2,4\}$对应子串ab和b。

我们发现，两个不同子串的endset要么是包含关系，要么不相交。假如子串$w_2$是$w_1$的后缀，那么显然$\text{endset}_{w_1}\subseteq \text{endset}_{w_2}$；否则，假如$w_1,w_2$互相不为后缀，此时如果有$p\in \text{endset}_{w_1}\cap \text{endset}_{w_2}$，那么从位置$p$为endpos可以看出要么$w_1$是$w_2$的后缀要么$w_2$是$w_1$的后缀，矛盾。“要么无交要么包含”的关系是树形结构的关系，可见给定字符串的所有子串的endset会形成一棵树，称为parent tree。其中，根节点可以看作空集$\text{endset}_{\varnothing}=\{1,2,\cdots,n\}$。容易发现，parent tree上从叶节点到根节点的路径上节点对于的子串恰好是叶节点的字符串长度从大到小的所有后缀，同一个节点上可能有多个子串，这些子串有相同后缀且长度连续（因为当我们去掉一个子串最左侧的字符时，endset要么不变要么扩大）。

状态转移

我们可以在parent tree上增加状态转移边来构造自动机。对于每个状态（一个endset），如果其中存在子串$s_0$使得$s_0$的右侧增加字符$c$得到的字符串$s_0+c$也是$s$的一个子串，那么我们就从$s_0$的endset向$s_0+c$的endset连一条状态转移边。我们证明，这样得到的自动机上接受且仅接受$s$的所有子串。

从空集对应的endset出发做状态转移，状态转移路径对应的字符串必然出现在当前endset当中。假设$w$是$s$的子串，那么沿着$w$从左到右的字符做状态转移，显然每一次状态转移边都存在，因此自动机能接受$w$；反之，如果$w$不是$s$的子串，那么不可能存在一个endset包含$w$，因此自动机不能接受$w$。证毕。

后缀自动机的构造应当保证以上状态转移是良定义的，也即每个状态关于每个字符只有一条状态转移边。如果一个状态中存在子串$s_0$能右侧增加$c$，则原串中存在一个位置有子串$s_0$且能增加$c$。这个状态中的最长串与$s_0$有相同的endpos，因此最长串一定也能做$c$的转移。因此当我们说一个状态能够转移$c$时，其中的所有子串都能做$c$的转移。我们要求所有子串在转移后拥有相同的endset。

后缀自动机的在线构造算法

下面我们介绍归纳地构造后缀自动机的算法。假如我们已经构造好了字符串$s$对应的后缀自动机，也即已经有了$s$的所有endset对应的状态，状态间的parent tree树边以及自动机的状态转移边。现在当我们要为$s$后侧加上字符$c$时，如何得到新的后缀自动机呢？

原来的后缀自动机已经能够接受$s$的所有子串，因此我们只需使得新增的$n+1$个以$c$为右端点的子串能被自动机接受，同时把这些子串产生的新的endpos合并到原来的endset当中。我们需要修改的只可能有：所有$s+c$的后缀的endset（可能有新增）；所有$s$的后缀的关于$c$的状态转移边。

首先，我们必须新增endset $\{n+1\}$，它至少包含了$s+c$这个字符串，或许还包含它的若干长度连续递减的后缀。endset $\{n\}$一定有且仅有一条状态转移边$c$指向$\{n+1\}$，我们把它增添上。原先$\{n\}$中的串在原串中都仅出现了一次，因此$+c$的endpos一定只可能是$n+1$，所以$\{n+1\}$中包含了所有这些串$+c$得到的串。比这些更短一些的后缀是parent tree上$\{n\}$的父节点$f$中的串（如果存在），这些串在原串中出现了不止一次，此时有两种情况：$f$中的串仅在末尾能够$+c$，也即$+c$后变得在原串中只出现一次了，那么这些串依然属于endset $\{n+1\}$，所以$f$也应向$\{n+1\}$连接状态转移边$c$，接着我们再找$f$的父节点，重复此过程；另一种可能是，$f$中存在串在$+c$后也出现在非末尾的位置，这意味着出现了一个包含$n+1$的更大的endset。设$f$转移$c$后的状态为$g$，如果$f$中最长的串$+c$恰好就是$g$中最长的串，说明$g$的endset是所有$f$中的最长串能够$+c$的那些位置，在加入$n+1$后$g$中应当包含$n+1$，原先那个不包含$n+1$的$g$的状态实际上已经不存在了（如果存在，则$f$中应当有更长的串，矛盾），同时$g$中串的所有后缀对应的endset（parent tree上到根节点路径上所有的点）都应该包括$n+1$，且原来那个不包含$n+1$的状态实际上已经不存在了，不用再去父节点修改，$g$的状态转移也与原来相同；如果$f$中最长的串$+c$不是$g$中最长的串，说明$g$中存在更长的以$c$结尾的串，但是这个更长的串不能出现在末尾$n+1$（否则说明当前$g$就是上一轮讨论过的状态，矛盾），因此此时$g$应当分裂成两个状态$g_1$和$g_2$，一个是包含$n+1$的endset，一个是不包含$n+1$的endset，这两个状态具有相同的状态转移，在parent tree上都$g_2$的父亲是$g_1$，$g_1$的父亲是$g$的父亲，修改完成。至此，我们已经讨论了所有$s+c$的后缀的endset和所有$s$的后缀关于$c$的状态转移边了，构造算法完成。

注意到，在每一次新增字符时，我们至多只会增加两个endset状态，因此后缀自动机的状态数是线性的。同时，通过均摊分析也可以证明总的构造复杂度也是$O(n)$的。后缀自动机是能够线性维护所有子串的算法。

后面的是之前写的。

后缀自动机的本质

​ 字符串匹配的问题（例如在字符串ababaabbababa中询问aba出现的次数），最简单的算法就是逐位比对。而人们发现，这样做远远没有达到数学上的最优化。这个问题之所以能够得到优化，是因为上面这个处理方法里我们做了无用功——我们没能充分利用好“历史信息”。这个历史信息就是：字符串经常自己和自己存在冗余，比如字符串的某个后缀很可能在许多不是后缀的位置出现。比如在abbabbababba中，后缀abba出现了三次。这是我们在匹配问题中可以加以利用的一种冗余。

​ 匹配问题中，最重要的信息就是子串的信息。我们总是在寻找一种高效的方法来把一个字符串的所有子串维护起来方便查找。对于这个问题，首先容易想到的就是把字符串$s$的每个后缀都插入一棵字典树中，这样从起点出发的任何一条路径都将对应$s$的一个子串。然而这样的字典树的复杂度还是$O(n^2)$的。但我们会发现，重复的子串正对应着重复的路径，如果能将重复的路径设法合并，也就是将字典树变成有向图，就可能可以优化复杂度。后缀自动机就是这么做的。它能够在$O(n)$的复杂度下完成构建，也能以$O(n)$的复杂度进行匹配。

​ 后缀自动机能够实现优化，在于它对子串进行了一种压缩。后缀自动机的一个状态（在图论里称之为节点，在自动机里称之为状态，其实是一回事）不只对应一个子串或一个位置，而是一系列子串和一系列位置。一个状态其实对应着一个集合，称之为endset。在理解所有后缀自动机的问题时，牢牢把握住endset合的内涵，就像双脚牢牢踩在地上一样。

​

​ 后缀自动机把每个endset作为它的状态。不同的endset合之间是有联系的。我们发现，比如对于某个子串$w$，$w$有后缀$w'$。$w$的endset（$S$）一定是被包含在$w'$的endset（$S'$）里的，因为所有$w$的endpos都可以作为$w'$的endpos，反过来却不一定。比如ababb中，ab的endset为$\{2,4\}$，b的endset为$\{2,4,5\}$。我们还发现，当同一个endset合表示不止一个子串时，这些串一定有着连续的长度，并且短的串一定是长的串的后缀。比如cabcab中，$\{3,6\}$对应cab、ab、b。因为当我们去掉$w$最左端的一个字符后，其endset要么不变，要么有所扩大。如果不变，那么被砍了之后的$w$依然属于该endset，串的连续性得到了保证。而如果有所扩大，那么新串势必不再属于这个集合了。所以该endset对应的是这样的一些连续被从左边砍掉的串。

​ 当一个串逐个被砍为自己的后缀时，对应的endset会不断扩大，最终扩大到全集（串变成“空”）。正因为一个串的endset是包含于其后缀的endset的，所有的endset会通过这种方式形成一棵树。这就是parent tree。从一个节点不断跳fa，也就是不断缩减为自己的后缀，最终会到达根节点（空）。

补充证明不可能两个endset集合互不包含但有交。考虑短的那个子串，矛盾。

​ 然而后缀自动机中“路径对应子串”的工作并不是通过parent tree的树边来完成的，而是通过“状态转移边”来完成的。要再次强调的是，后缀自动机的每个状态是一个“位置的集合”，同时也代表着以“这些位置”作为“endpos”的一系列子串。后缀自动机的每个状态是非常具体的有意义的，而不是一个仅仅起过渡作用的抽象的有向图上的节点。换句话说，状态比状态转移边要重要得多。状态转移边只是为了维护子串，并且在这些子串之间穿梭。而相比之下，parent tree的边在理解上是比状态转移边更贴近本质的东西。当我们说“某个状态”的时候，脑子里应该浮现出一个长的字符串，里面有着若干个相同的子串以及这些子串的后缀。

​ 而所谓“状态转移”就是针对状态对应的子串说的。我们暂且假设同一个状态中的所有不同的子串是可以统一考虑的，于是对于这些子串来说，像“在右侧增加字符a”这样的变化，就可以称作状态转移。状态转移其实就是计算这些子串在右端加上一个字符之后子串及其对应的endset要发生一次什么样的变化：在那些子串里，在原串的位置上没有后接a的那些势必不可能出现在新的集合里了，而所有那些后接a的一定都是会出现在新集合里的，这些位置就构成了新的状态。有没有可能有别的位置出现在新状态里？如果有，那么那个位置去掉右端的$a$之后的位置一定会在原来的状态里，因此不会有别的位置出现。换句话说，新状态的endset合里的元素个数不会增加，新的位置都是其中一些旧的位置（后接a的哪些位置）向右平移一格构成的。

后缀自动机的构造算法

​ 构造后缀自动机就是构造parent tree的树边（称为后缀链接）和状态转移边。通常情况下，我们不需要把每个状态的endset具体记录下来。实际上，endset还会在构造的过程中发生变化，比如从$\{2,4\}$变成$\{2,4,7\}$，但这个变化不会在自动机的结构上显现出来。

​ 我们采用递推的方式来构造后缀自动机，即我们假设我们已经有了一个接受字符串$s$的完好的后缀自动机，现在要将它改造为一个接受字符串“$s'=s+字符c$”的后缀自动机。

​ 表面上我们是在思考parent tree和状态转移边，实际上我们只需要思考新出现的这$n+1$个子串（即$s'$的每个后缀）将对原来的endset合产生什么样的影响。

​ 设$s$的长度为$n$，我们首先肯定有一个新的endset$\{n+1\}$，因为整个新串$s'$的endset只能是$\{n+1\}$。

​ 接着，我们从长到短逐个考察原串$s$的后缀$x$（注意是$s$不是$s'$）。（一般而言）最开始的时候，$x+c$都没有在别的位置出现过，这些$x$不会对endset产生任何破坏。$x$越来越短，突然，$x+c$在某个（些）地方出现了。对于这样的$x$，它对应的endset肯定要增加一个新元素$n+1$了。

​ 可这里有个问题。先前我们在理解状态转移的时候，假设了同一个状态中的所有不同的子串是可以统一考虑的，而现在还可以这样吗？像abcabc这样的串是可以的，因为当我们发现abc这个子串的endset时，这个endset维护着abc、bc、c，新的字符加进来后，这些被维护的子串的endset全都从$\{3\}$变作了$\{3,6\}$，换句话说原先的状态是作为一个整体发生变化的。可碰到eabceabcabc这样的串的时候就麻烦了。当我们发现abc这个子串的时候，原先的abc的endset$\{4,8\}$还包括着eabc，它还带着一个前缀e。而这个串对应的endset不会从$\{4,8\}$变成$\{4,8,11\}$。于是我们发现，原先的endset必须裂成两个。

​ 怎么判断要不要裂开呢？只需要看状态转移前后的两个endset里最长的那个子串。在abcabc里，ab的endset里最长的是ab，abc的endset里最长的是abc，后者的长度刚好是前者长度加一。所以我们知道它不用裂开，因为原先的endset里的串一定没有带前缀，如果有，那长度之间的关系就不只是加一了。而eabceabcabc里，由于长度加了二，所以必须裂开了。另外提一句，转移后的endset里最长串的长度是不可能比转移前小的，因为原先的最长串加上转移的字符一定会出现在转移后的状态里。

​ 然后再来看如何构建状态转移边和后缀链接。假设新字符$c$是第$n+1$个。我们首先找到$\{n\}$这个状态，然后在parent tree上跳fa。一路上碰到的每个状态都要连向$\{n+1\}$的状态转移边。如果当前状态$p$存在$c$这个转移，设转移后的状态为$q$。我们要在构建的过程中顺便维护一个maxlen，记下每个endset维护的最长的串的长度。此时就判断maxlen(p)+1是否等于maxlen(q)。如果是，那么不用裂开，$\{n+1\}$的后缀链接就是$q$了，除此之外不需要做任何改变，也不用继续跳fa了，因为$p$已经有了$c$的转移，如果原先的后缀自动机是正确的那么$p$的后缀自然也会有向$c$的转移，只不过这些转移对应的endset都已经增加了$n+1$这个元素，但是这个变化不会对自动机的结构有任何影响。如果不是，那么我们需要构建一个新的状态（有$n+1$的那个状态），这个状态是从$p$转移过来的（至于$q$，原先就有带有前缀的那个串向$q$转移，不用担心它被孤立），新状态的状态转移边应该是和$q$全部一样的（由此我们还可以发现，具有完全相同的状态转移也是“能被统一为一个状态”的条件）。$n+1$的后缀链接也就是这个新状态了。同时，原来的$p$的后缀（不只有$p$本身）的状态转移有一部分可能依然指向$q$，应当把他们修改为这个新状态。

inline void sam_insert(int pos, int c){
	las = cur;
	cur = ++cnt;
	mxl[cur] = pos;
	sz[cur] = 1;
	for(int p = las; p != 0; p = fa[p]){
		if(trans[p][c] != 0){
			int q = trans[p][c];
			if(mxl[p]+1 == mxl[q]){
				fa[cur] = q;
				return;
			}else{
				++cnt;
				mxl[cnt] = mxl[p]+1;
				fa[cur] = cnt;
				fa[cnt] = fa[q];
				fa[q] = cnt;
				memcpy(trans[cnt], trans[q], sizeof(trans[q]));
				for(; p != 0 && trans[p][c] == q; p = fa[p]){
					trans[p][c] = cnt;
				}
				return;
			}
		}else{
			trans[p][c] = cur;
		}
	}
	fa[cur] = 1;
}

使用后缀自动机

计算endset大小

​ endset的大小是不容易在构建的时候维护的，因为构建的时候大多数endset大小会一连串的变化。我们可以对构建好后的parent tree进行一个简单的dp来解决这个问题。

​ 一个父节点的所有子节点的endset是不会重叠的。因为父节点维护的是子节点的公共后缀，子节点之间之所以不同是因为他们维护的串都是父节点的串加上不同的前缀。同时，子节点endset都包含于父节点，很容易认为子节点的并集就是父节点了。但是这里有一种例外。假如说某个父节点维护了一个顶头的串（即原串的一个前缀），那显然不会有比这个串更长的串出现在同一个右端点了。但是这个串有可能出现在别的位置，这就导致顶头的这个串的位置在子节点中消失了：在abcabc中，状态$\{3,6\}$的子节点只有$\{6\}$。所以，我们可以在构建后缀自动机的时候标记好所有这些顶头的串（其实就是每一次诞生的整个新串），这样后面在统计时他们就会自动被累计进去了。叶节点的endset大小一定为1。因为如果超过1，长的那个就可以单独成串。