施工中。。

后缀自动机 (suffix automaton, SAM)

SAM 的概述

可以解决很多字符串问题的强大工具。是一个可以处理字符串 $SS$ 的所有后缀的 最小的 确定性有限自动机。

SAM 的定义

• SAM 是一张有向无环图。结点被称作 状态 ，边被称作状态间的 转移 。
• 图存在一个源点 $t_{0}t\_0$ ，称作 初始状态 ，其它各结点均可从 $t_{0}t\_0$ 出发到达。
• 每个 转移 都标有一些字母。从一个结点出发的所有转移均 不同 。
• 存在一个或多个 终止状态 。如果我们从初始状态 $t_{0}t\_0$ 出发，最终转移到了一个终止状态，则路径上的所有转移连接起来一定是字符串 $SS$ 的一个后缀。 的每个后缀均可用一条从 $t_{0}t\_0$ 到某个终止状态的路径构成。
• 在所有满足上述条件的自动机中，SAM 的结点数是最少的。

合法 SAM 的举例

关于字符串 $S=ababaS\; =\; ababa$ ，一些常见的不合法的构造。

• 若出现闭环，则不是合法的。 [图]
• 若出现出现多余节点，则不是合法的。 [图]

endpos 的引入

引入了 $endposendpos$ 我们就能更好的线性构造 $SAMSAM$ 。

endpos 的定义

对于字符串 $SS$ 的一个子串 $tt$ ， $endpos(t)endpos(t)$ 为 $tt$ 在 $SS$ 中出现的最后一个字符的位置 （记一个字符为 $11$ 号位）。我们把 $endposendpos$ 相同的字符串归为一个 $endposendpos$ 等价类。

endpos 举例

对于 $S=ababaS\; =\; ababa$ 来说， $endpos(\mathrm{"}ba\mathrm{"})=3,5endpos("ba")\; =\; 3,5$ $endpos(\mathrm{"}a\mathrm{"})=1,3,5endpos("a")\; =\; 1,3,5$ 。

关于 endpos 的性质

• 对于 $SS$ 来说，它的两个子串 $w,vw,v$ ，那么 $endpos(w),endpos(v)(\mathrm{\mid }v\mathrm{\mid }\le \mathrm{\mid }w\mathrm{\mid })endpos(w),endpos(v)\; (|v|\; \backslash leq\; |w|)$ 只有两种关系。要么 $endpos(w)\subseteq endpos(v)endpos(w)\; \backslash subseteq\; endpos(v)$ 。要么 $endpos(w)\cap endpos(v)=\mathrm{\varnothing }endpos(w)\; \backslash cap\; endpos(v)\; =\; \backslash varnothing$ 。其实很好理解，因为如果两个字符串的 $endposendpos$ 不同，那么如果它们最后一个字符都不一样，那么肯定是空集。因此当两个字符串的 $endposendpos$ 只要有一个是相同的，那么一定存在一个位置，使 $vv$ 作为了 $ww$ 的后缀出现，那么所有出现了 $ww$ 的位置 $vv$ 一定要出现。因此一定是包含关系。
• 一个 $endposendpos$ 等价类中各个字符串的长度一定不相同，而且刚好覆盖了 $[le{n}_{min},le{n}_{max}][len\_\{min\},len\_\{max\}]$ 。可以反证，如果出现了相同长度的串，而 $endposendpos$ 又相同显然串有至少有一个字符是矛盾的。
• 一个 $endposendpos$ 等价类中的字符串一定是最长串的后缀。由第一点可以知道 $endpos(w)\subseteq endpos(v)endpos(w)\; \backslash subseteq\; endpos(v)$ 那么每次只有 $ww$ 出现， $vv$ 也同时作为后缀出现。

link 引入

引入 $linklink$ （后缀链接）有助于我们利用 $endposendpos$ 的性质。

link 的定义

在一个 $endposendpos$ 的等价类中我们把最长字符串令为 $ww$ ，最短字符串令 $vv$ ，那么这个 $endposendpos$ 等价类中的字符串包含了长度为 $[\mathrm{\mid }v\mathrm{\mid },\mathrm{\mid }w\mathrm{\mid }][|v|,|w|]$ 的 $ww$ （包括 $ww$ ）的后缀。那么 $ww$ 一定有一个后缀在其它的 $endposendpos$ 等价类中（定义空后缀的 $endposendpos$ 为全集）。那么这个 $endposendpos$ 的后缀链接就应链接到 $ww$ 最长的在其它等价类的后缀的等价类。

link 举例

[图]

关于 link 的性质

• 用 $linklink$ 链接的 $endposendpos$ 等价类最后会形成一个以 $t_{0}t\_0$ 为根节点的树。并且这棵树的节点与用 $endposendpos$ 集合包含关系构建的是一样的。关于它是一棵树是很显然的，因为最后一定会链接到空串，也就是 $t_{0}t\_0$ ，至于因为根据 $endposendpos$ 的性质，当前串的 $endposendpos$ 一定是后缀的子集，而 $endpos(s)⫋endpos(link(s))endpos(s)\; \backslash subsetneqq\; endpos(link(s))$ 因此两者是等价的。也就是说后缀链接构成的树本质上是 $endposendpos$ 集合构成的一棵树。
• 若 $vv$ 是一个等价类 $SS$ 的最短串，那么 $len(link(S))+1=\mathrm{\mid }v\mathrm{\mid }len(link(S))\; +\; 1\; =\; |v|$ 。
• 也就是说如果我们从任意状态 $v_{0}v\_0$ 开始顺着后缀链接遍历，总会到达初始状态 $t_{0}t\_0$ 。这种情况下我们可以得到一个互不相交的区间 $[minlen(v),len(v)][minlen(v),len(v)]$ 的序列，且它们的并集形成了连续的区间 [0,len(v)] 。