后缀自动机 (suffix automaton, SAM) 是一个能解决许多字符串相关问题的有力的数据结构。

字符串的 SAM 可以理解为给定字符串的 所有子串 的压缩形式。值得注意的事实是, SAM 将所有的这些信息以高度压缩的形式储存。对于一个长度为 \(n\) 字符串,它的空间复杂度仅为 \(O(n)\) 。此外,构造 SAM 的时间复杂度仅为 \(O(n)\) (这里我们将字符集的大小 \(\|\sum \|\) 看作常数,否则时间复杂度和空间复杂度均为 \(O(nlog\|\sum \|)\) )。

定义

字符串 \(s\) 的 SAM 是一个接受 \(s\) 的所有后缀的最小 DFA 确定性有限自动机或确定性有限状态自动机)。

具体来说:

  • SAM 是 DAG 。结点被称作状态,边被称做转移
  • 图有一个源点 \(t_0\) ,称作 初始状态 ,其它各结点均可从 \(t_0\) 出发到达。
  • 每个 转移 都标有一些字母。从一个结点出发的所有转移均 不同 
  • 存在一个或多个 终止状态 。如果我们从初始状态 \(t_0\) 出发,最终转移到了一个终止状态,则路径上的所有转移连接起来一定是字符串 \(s\) 的一个后缀。 的每个后缀均可用一条从 \(t_0\) 到某个终止状态的路径构成。
  • 在所有满足上述条件的自动机中, SAM 的结点数是最少的。

重要的性质

  • SAM 最重要的性质就是,它包含了字符串 \(s\) 的所有子串信息。任意从初始状态 \(t_0\) 开始的路径,如果我们将转移路径上的标号写下来,都会形成 \(s\) 的一个 子串 。也就是说子串对应一条路径(从 \(t_0\) 出发)。
  • 到达某个状态的路径可能不止一条。

构造 SAM

一些概念和符号

结束位置 endpos

对于字符串 \(s\) 的任意非空子串 \(t\) ,我们记 \(endpos(t)\) 为字符串 \(s\) 中 \(t\) 的所有结束位置。

为了方便,我们规定 \(endpos(t_0)=\{-1,0,\cdots ,|S|-1\}\) 。

可以得到一些结论:

  1. 两个非空子串 \(u\) 和 \(w\) ( \(|u|\le |w|\) )的 \(endpos\) 相同,但且仅当字符串 \(u\) 是 \(w\) 的后缀。
  2. 考虑两个非空子串 \(u\) 和 \(w\) ( \(|u|\le |w|\) )。如果 \(u\) 是 \(w\) 的一个后缀,那么有 \(endpos(w) \subseteq endpos(u)\) ;否则就是 \(endpos(w)\bigcap endpos(u) = \emptyset \)。
  3. 任意相等的 \(endpos\) 对应的子串,较短者为较长者的后缀。
后缀链接 link

对于 SAM 中某个不是 \(t_0\) 的状态 \(v\) 。定义\(w\) 为 \(endpos(w)=endpos(v)\) 中长度最长的一个。

我们知道字符串 \(w\) 的前几个后缀\(t\) (按长度降序考虑)满足 \(endpos(t) \subseteq endpos(w)\) ,而剩下的不满足,那么 \(v\) 的后缀链接在不满足要求的最长的子串上。

例如对于字符串 “abcbc” , \(link_{“abcbc”}=”bc”\) , \(link_{“abcb”}=”b”\) 。

  1. 所有的后缀链接构成一棵根结点为 \(t_0\) 的树。
  2. 通过 \(endpos\) 集合构造的树(每个子节点都包含在父节点中)与通过后缀链接 link 构造的树相同。
其他的符号定义
  • 对于每一个状态 \(v\) 表示多个子串。我们记 \(longest(v)\) 为其中最长的一个字符串,记 \(len(v)\) 为它的长度;同样地,记 \(shortest(v)\) 为其中最短的一个字符串,记 \(minlen(v)\) 为它的长度。
  • 对于每一个状态 \(v\) ,有 \(minlen(v)=len(link(v))+1\) 。

构造

现在我们可以学习构造 SAM 的算法了。这个算法是 在线 算法,我们可以逐个加入字符串中的每个字符,并且在每一步中对应地维护 SAM ,所以 SAM 的构造过程是一个增量构造。

假设我们已经有了字符串 \(S\) 的 SAM ,只需要考虑如何修改得到 \(S+c\) ( \(c\) 为一个字符)的 SAM 。

例如我们已经有了下图的 SAM (黑色的为后缀链接,灰色的为字符 \(c\) 的转移边):

这里,显然 \(v_4\) 到 \(v_6\) 为 \(v_3\) 的后缀,所以如果 \(v_3\) 中的字符串添加一个字符后得到的字符串存在于原母串中,则 \(v_4\) 到 \(v_6\) 中的字符串添加一个字符后得到的字符串一定也存在于原母串中,而 \(v_2\) 中添加一个字符后得到的字符串可能会不存在于母串中。图中我们假设 \(v_2\) 是第一个满足「添加一个字符后得到的字符串不存在于母串中」的节点。

现在加入新的字符 \(c\) ,出现了一些新的子串,而且它们都是新母串的后缀。我们设这些新的字符串被新结点 \(u\) 所表示,显然 \(len(u)=len(v_1)+c,minlen(u)=minlen(v_2)+c\) 。

新加入的字符 \(c\) 导致新出现了 \(|S|+1\) 个后缀,这些后缀都需要新的节点来表示。首先,节点 \(u\) 表示了长度大于等于 \(min(u)+1\) 的后缀,而更短的后缀已经可以由 \(d\) 及其后缀链接的路径上的节点来表示。所以,DFA 的性质已经被满足。接下来考虑前缀树。

  • 首先,如果不存在这样的 \(v_3\) 满足有字符 \(c\) 的出边,则需要将 \(u\) 的后缀链接联想其实结点 \(start\) ,因为新出现的 \(|S|+1\) 个后缀都需要用结点 \(u\) 来表示,即 \(minlen(u)=1\) 。
  • 如果 \(d\) 中最长的字符串为 \(v_3\) 中最长的字符串加上字符 \(c\) 后得到的,因为 \(len(d)=len(v_3)+1\) , \(len(u)=minlen(v_2)+1\) , \(len(v_3)=len(v_2)-1\) ,所以 \(len(d)=minlen(v_2)-1+1=minlen(u)\) ,所以 \(u\) 的后缀链接连向 \(d\) 。
  • 如果不满足 \(d\) 中最长的字符串为 \(v_3\) 中最长的字符串加上字符 \(c\) 后得到的,那么一定有 \(max(d) > max(v_3)+1\) ,因为字符串 \(max(v_3) + c\) 一定在 \(d\) 中,并且存在另一个异于 \(v_i\) 的结点 \(t\) ,满足 \(link(t)=v_3\) ,且 \(t\) 有连向 \(d\) 的转移边。
  • 此时我们不能将 \(u\) 的后缀链接连向 \(d\) ,因为 \(d\) 中的字符串不全是 \(u\) 的后缀。所以我们需要将 \(d\) 拆成两个点,一个点 \(n\) 表示长度小于等于 \(max(v_3)+1\) 的子串,另一个点 \(o\) 表示长度更大的子串。
  • 此时,结点 \(n\) 显然已经全部都是\(u\) 的后缀了,那么新结点 \(u\) 的后缀链接 \(link(u)=n\) 。

注意到在构造过程中,每个子串都有对应的节点来表示,并且每个节点的 \(endpos\) 集合不会相同(根据对前缀树结构的改变,容易证明这一结论),所以构造算法是正确的。

模板

例题

【Hihocoder1445】重复旋律5

显然对于每一个状态\(v\),它所代表的不同子串个数是\(len[v]-len[link[v]]\)。

所以整个字符串中不同子串的个数就是\(\sum_{i=0}^{sz} (len[v]-len[link[v]])\)。

【Hihocoder1449】重复旋律6

【Hihocoder1449】后缀自动机三·重复旋律6

【Hihocoder1457】重复旋律7

【Hihocoder1457】后缀自动机四·重复旋律7

【Hihocoder1465】重复旋律8

【Hihocoder1465】后缀自动机五·重复旋律8

【Hihocoder1466】重复旋律9

【Hihocoder1466】后缀自动机六·重复旋律9


发表评论

电子邮件地址不会被公开。 必填项已用*标注