直观上,字符串的 SAM 可以理解为给定字符串的 所有子串 的压缩形式。值得注意的事实是,SAM 将所有的这些信息以高度压缩的形式储存。对于一个长度为 n 的字符串,它的空间复杂度仅为 O(n)。此外,构造 SAM 的时间复杂度仅为 O(n)。准确地说,一个 SAM 最多有 2n-1 个节点和 3n-4 条转移边。
我们稍后将会用这个假设来介绍构造 SAM 的算法。我们将发现,SAM 需要满足的所有性质,除了最小性以外都满足了。由 Nerode 定理我们可以得出最小性(不会在这篇文章中证明)。
由 \operatorname{endpos} 的值我们可以得到一些重要结论:
引理 1: 字符串 s 的两个非空子串 u 和 w(假设 \left|u\right|\le \left|w\right|)的 \operatorname{endpos} 相同,当且仅当字符串 u 在 s 中的每次出现,都是以 w 后缀的形式存在的。
引理显然成立。如果 u 和 w 的 \operatorname{endpos} 相同,则 u 是 w 的一个后缀,且只以 s 中的一个 w 的后缀的形式出现。且根据定义,如果 u 为 w 的一个后缀,且只以后缀的形式在 s 中出现时,两个子串的 \operatorname{endpos} 相同。
引理 2: 考虑两个非空子串 u 和 w(假设 \left|u\right|\le \left|w\right|)。那么要么 \operatorname{endpos}(u)\cap \operatorname{endpos}(w)=\varnothing,要么 \operatorname{endpos}(w)\subseteq \operatorname{endpos}(u),取决于 u 是否为 w 的一个后缀:
\begin{cases} \operatorname{endpos}(w) \subseteq \operatorname{endpos}(u) & \text{if } u \text{ is a suffix of } w \\ \operatorname{endpos}(w) \cap \operatorname{endpos}(u) = \varnothing & \text{otherwise} \end{cases}
证明:如果集合 \operatorname{endpos}(u) 与 \operatorname{endpos}(w) 有至少一个公共元素,那么由于字符串 u 与 w 在相同位置结束,u 是 w 的一个后缀。所以在每次 w 出现的位置,子串 u 也会出现。所以 \operatorname{endpos}(w)\subseteq \operatorname{endpos}(u)。
记 w 为等价类中最长的字符串、u 为等价类中最短的字符串。由引理 1,字符串 u 是字符串 w 的真后缀。现在考虑长度在区间 [\left|u\right|,\left|w\right|] 中的 w 的任意后缀。容易看出,这个后缀也在同一等价类中,因为这个后缀只能在字符串 s 中以 w 的一个后缀的形式存在(也因为较短的后缀 u 在 s 中只以 w 的后缀的形式存在)。因此,由引理 1,这个后缀和字符串 w 的 \operatorname{endpos} 相同。
如果我们还想知道哪些状态是 终止状态 而哪些不是,我们可以在为字符串 s 构造完完整的 SAM 后找到所有的终止状态。为此,我们从对应整个字符串的状态(存储在变量 \textit{last} 中),遍历它的后缀链接,直到到达初始状态。我们将所有遍历到的节点都标记为终止节点。容易理解这样做我们会准确地标记字符串 s 的所有后缀,这些状态都是终止状态。
在下一部分,我们将详细叙述算法每一步的细节,并证明它的 正确性。 因为我们只为 s 的每个字符创建一个或两个新状态,所以 SAM 只包含 线性个 状态。
现在我们来估计不连续的转移的数量。令当前不连续转移为 (p,\,q),其字符为 c。我们取它的对应字符串 u+c+w,其中字符串 u 对应于初始状态到 p 的最长路径,w 对应于从 q 到任意终止状态的最长路径。一方面,每个不完整的字符串所对应的形如 u+c+w 的字符串是不同的(因为字符串 u 和 w 仅由完整的转移组成)。另一方面,由终止状态的定义,每个形如 u+c+w 的字符串都是整个字符串 s 的后缀。因为 s 只有 n 个非空后缀,且形如 u+c+w 的字符串都不包含 s(因为整个字符串只包含完整的转移),所以非完整的转移的总数不会超过 n-1。
观察 实现 中的结构体的每个变量。实际上,尽管 SAM 本身由 next 组成,但 SAM 构造算法中作为辅助变量的 link 和 len 在应用中常常比 next 重要,甚至可以抛开 next 单独使用。
设字符串的长度为 n,考虑 extend 操作中 cur 变量的值,这个节点对应的状态是执行 extend 操作时的当前字符串,即字符串的一个前缀,每个前缀有一个终点。这样得到的 n 个节点,对应了 n 个不同的 终点。设第 i 个节点为 v_i,对应的是 S_{1 \ldots i},终点是 i。姑且把这些节点称之为“终点节点”。
考虑给 SAM 赋予树形结构,树的根为 0,且其余节点 v 的父亲为 \operatorname{link}(v)。则这棵树与原 SAM 的关系是:
每个节点的终点集合等于其 子树 内所有终点节点对应的终点的集合。
在此基础上可以给每个节点赋予一个最长字符串,是其终点集合中 任意 一个终点开始 往前 取 len 个字符得到的字符串。每个这样的字符串都一样,且 len 恰好是满足这个条件的最大值。
每个状态 i 对应的子串数量是 \operatorname{len}(i)-\operatorname{len}(\operatorname{link}(i))(节点 0 例外)。注意到 \operatorname{link}(i) 对应的字符串是 i 对应的字符串的一个后缀,这些子串就是 i 对应字符串的所有后缀,去掉被父亲“抢掉”的那部分,即 \operatorname{link}(i) 对应字符串的所有后缀。