自动机入门——后缀自动机

数据结构简介

后缀自动机是一个可以解决许多字符串相关问题的有力的数据结构，字符串的 SAM 可以理解为给定字符串的所有子串的压缩形式，SAM 的空间复杂度和构造的时间复杂度均为线性的，准确的说，一个 SAM 最多有 \(2n-1\) 个节点和 \(3n-4\) 条转移边。

定义

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

换句话说：

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

性质

SAM 包含关于字符串 \(s\) 的所有子串的信息，任意从初始状态开始的路径，如果我们将转移路径上的字符写下来都会形成一个 \(s\) 的子串，反之每一个 \(s\) 的子串对应从 \(t_0\) 开始的某条路径。

为了简化表达，我们称子串对应一条路径，反过来，一条路径也可以对应一个子串。

到达某个状态的路径可能不止一条，因此我们说一个状态对应一个字符串的集合，这个集合的每一个元素对应这些路径。

构造

结束位置

结束位置 \(endpos\) 是一个比较重要的概念。

考虑字符串 \(s\) 的任意非空子串 \(t\) ，我们记 \(endpos(t)\) 为在字符串 \(s\) 中 \(t\) 出现的所有位置（用右端点的结束位置来代表），例如串 \(\text{abbaabab}\) 中 \(\text{ab}\) 的结束位置为 \(1,5,7\)。两个子串的 \(t_1\)，\(t_2\) 的 \(endpos\) 集合可能相等，这种二元关系显然是等价关系。我们可以根据它们的 \(endpos\) 集合把所有子串划分为若干等价类。

SAM 中的每一个状态都对应一个等价类，也就是说 SAM 的状态总数为等价类的个数 \(+1\)（初始节点）。

• 引理 \(1\)

  字符串 \(s\) 的两个不同的非空子串 \(u,w\) ，（假设 \(|u|<|w|\)）的 \(endpos\) 相同，当且仅当字符串 \(u\) 在 \(s\) 中的每次出现，都是以 \(w\) 的后缀形式存在的。

  证明：引理显然成立。

• 引理 \(2\)

  考虑两个非空子串 \(u,w\) （假设 \(|u|\le |w|\)），那么要么 \(endpos(u)\cap endpos(w)=\varnothing\) ，要么 \(endpos(w)\subseteq endpos(u)\) ，这取决与 \(u\) 是否为 \(w\) 的一个后缀，如果不是，就是前者，否则就是后者。

  证明：其实也比较显然，因为如果不是后缀，显然 \(w\) 出现的地方 \(u\) 不可能出现，所以是空集，如果是后缀，那么长度小的有可能出现在更多地方，并且一定在 \(w\) 都出现的地方出现过。

• 引理 \(3\)

  考虑一个 \(endpos\) 等价类，对于同一等价类中的任意两个子串，较短者为较长者的后缀，且该等价类中的子串长度是连续的。

  证明：前面这个后缀关系是显然的，我们来证明它们是连续的。如果不连续，那么设字符串 \(q\) 为夹在两个属于同一等价类的字符串 \(s,t(|s|<|t|)\) 之间的一个字符串，且 \(q\) 为 \(t\) 的后缀，\(s\) 是 \(q\) 的后缀，根据引理 \(2\) ，不难推出矛盾。

通过 SAM 的转移，即一些有向边，通过不同的方式走到状态 \(u\) ，我们就可以得到状态 \(u\) 对应的等价类所对应的所有字符串。

后缀链接 link

考虑 SAM 中某一个不是 \(t_0\) 的状态 \(v\) ，我们已经知道，状态 \(v\) 对应于具有相同 \(endpos\) 的等价类，设 \(w\) 是最长的一个，那么所有等价类中的字符串都是 \(w\) 的后缀。

我们还知道字符串 \(w\) 的前几个后缀全部包含于这个等价类，且所有其它后缀都在其他的等价类中，我们记 \(t\) 为最长的一个后缀，包含 \(t\) 的等价类不是 \(v\)。然后将 \(v\) 的后缀链接连到 \(t\) 的等价类所代表的状态上。

为了方便，我们规定：\(endpos(t_0)=\{-1,0,...,|s|-1\}\) 。

• 引理 \(4\)

  所有的后缀链接构成一棵根节点为 \(t_0\) 的树。

  比较显然，首先一定有 \(n-1\) 条边，其次因为字符串长度递减，所以不会出现环。然后一直递减，一定会到达初始状态 \(t_0\) 。

• 引理 \(5\)

  通过 \(endpos\) 集合构造的树（每个子节点的 \(subset\) 都包含在父节点的 \(subset\) 中）与通过后缀链接 \(link\) 构造的树相同。

  由引理 \(2\) ，这种实质是后缀关系的 \(endpos\) 能够形成一棵树。我们考虑不是 \(t_0\) 的状态 \(v\) ，显然有 \(endpos(v)\subsetneq endpos(link(v))\)。所以定理成立。

  但是需要注意的是，这棵树上，儿子节点的 \(endpos\) 集合不一定是父亲节点的一个划分，反例就是父亲节点的状态包含原字符串上的一个前缀。如果不包含前缀的话，性质是成立的。

小结

• \(s\) 的子串可以被划分成多个等价类。
• SAM 由若干状态构成，其中每一个状态对应一个等价类。对于每一个状态 \(v\) ，一个或多个子串与之匹配，我们记 \(longest(v)\) 为里面最长的一个，记 \(len(v)\) 为它的长度，记 \(shortest(v)\) 为最短的子串，它的长度为 \(minlen(v)\) ，那么所有字符串的长度恰好覆盖 \([minlen(v),len(v)]\) 中的每一个整数。
• 后缀链接可以定义为连接到对应某个状态满足 \(longest(v)\) 的长度为 \(minlen(u)-1\) 且是后缀关系的一条从 \(u\) 到 \(v\) 的边。后缀链接形成了一棵以 \(t_0\) 为根节点的内向树。这棵树也表示 \(endpos\) 集合间的包含关系。
• 我们有 \(minlen(v)=len(link(v))+1\)
• 如果我们从 \(v_0\) 开始一直走到 \(t_0\) ，那么沿途所有字符串的长度形成了连续的区间 \([0,len(v_0)]\)。

算法

这个算法是一个在线算法，可以逐个加入字符串中的每个字符并在每一步维护 SAM。

一开始 SAM 只包含一个状态 \(t_0\) ，编号为 \(0\) ，对于状态 \(t_0\) 我们指定 \(len=0,link=-1\) 。（这里 \(-1\) 就是一个虚拟状态）

现在任务转化为实现给当前字符串添加一个字符 \(c\) 的过程，算法流程如下：

• 令 \(last\) 为添加字符 \(c\) 之前，整个字符串对应的状态。
• 创建一个新的状态 \(cur\) ，并将 \(len(cur)\) 赋值为 \(len(last)+1\) 。
• 现在我们从状态 \(last\) 开始按以下流程进行：如果没有字符 \(c\) 的转移，我们就添加一个到状态 \(cur\) 的转移，遍历后缀链接，如果在某个点已经存在字符 \(c\) 的转移，我们就停下来，并将这个状态标记为 \(p\) 。
• 如果没有找到这样的状态 \(p\) ，我们就到达了虚拟状态 \(-1\) ，我们将 \(link(cur)\) 赋值为 \(0\) 并退出。
• 假设现在我们找到了一个状态 \(p\) ，其可以通过字符 \(c\) 转移，我们将转移到的状态记为 \(q\) 。
• 如果 \(len(p)+1=len(q)\) ，我们只需要将 \(link(cur)\) 赋值为 \(q\) 并退出。
• 否则，我们需要复制状态 \(q\) ，我们创建一个新的状态 \(clone\) ，复制 \(q\) 的除了 \(len\) 的值以外的所有信息（后缀链接和转移）。我们将 \(len(clone)\) 赋值为 \(len(p)+1\) 。复制之后，我们将后缀链接从 \(cur\) 指向 \(clone\) ，也从 \(q\) 指向 \(clone\) 。最终我们需要使用后缀链接从状态 \(p\) 往回走，只要存在一条通过 \(p\) 到状态 \(q\) 的转移，就将该转移重新定向到状态 \(clone\) 。
• 以上三种情况，在完成这个过程之后，我们将 \(last\) 的值更新为 \(cur\)。

因为我们只对 \(s\) 的每一个字符建立一个或两个新状态，所以 SAM 只包括线性个状态。

正确性证明

• 如果一个转移 \((p,q)\) 满足 \(len(p)+1=len(q)\) ，则我们称这个转移是连续的。否则，即当 \(len(p)+1<len(q)\) 时称其为不连续的。连续的转移是固定的，而不连续的转移可能会改变。

• 为了避免引起歧义，我们称 SAM 中插入当前字符 \(c\) 之前的字符串为 \(s\) 。

• 算法从创建一个新状态 \(cur\) 开始，对应于整个字符串 \(s+c\) ，我们创建一个新的节点的原因很清楚，就是要创建一个包含 \(endpos(s+c)\) 的等价类。

• 在创建一个新的状态之后，我们会从对应整个字符串 \(s\) 的状态通过后缀链接进行遍历，对于每一个状态，我们尝试添加一个通过字符 \(c\) 到新状态 \(cur\) 的转移。然而我们只能添加原有转移不冲突的转移。因此我们只要找到已存在的 \(c\) 的转移，我们就必须停止。

• 换句话说，当我们加入一个字符 \(c\) 的时候，会产生 \(|s|\) 个新的后缀，我们不断跳后缀链接，其实就是不断跳 \(s\) 的后缀，然后如果不冲突我们就连一条到 \(cur\) 的边。

• 如果不存在冲突，也就是说我们到达了虚拟状态 \(-1\) ，那意味着我们为所有 \(s\) 的后缀所对应的状态添加了转移 \(c\) ，这同时也意味着 \(c\) 之前从来没有在字符串中出现过，所以显然 \(cur\) 的后缀链接为 \(0\) 。

• 否则，存在一个 \(p\) 到 \(q\) 的转移，如果这个转移连续，这表明这个集合仍然满足是一个等价类，因为 \(q\) 中的字符串一定是由 \(p\) 和 \(p\) 的父亲经过转移得到的。所以我们直接把 \(cur\) 的后缀链接连上来就可以。

• 反之，\(p\) 一定有多个儿子，且某个儿子能转移到 \(q\)，这使得 \(q\) 中的字符串某些 \(endpos\) 会发生变化，某些不会变化，我们要把它分裂成两个状态，一个是变化的，一个是不会变化的，变化的那些就是 \(p\) 和 \(p\) 的父亲转移得到的字符串，变化的原因是我们往整个字符串 \(s\) 的末尾加了一个字符。分裂之后维护后缀链接即可。

对操作次数为线性的证明

一下我们认为字符集的大小为常数。

我们考虑算法的各个部分，有三处时间复杂度不明显是线性的：

• 第一处是遍历所有状态 \(last\) 的后缀链接，添加字符 \(c\) 的转移。
• 第二处是当状态 \(q\) 被复制到一个新的状态 \(clone\) 时复制转移的过程。
• 第三处修改指向 \(q\) 的转移，将它们重定向到 \(clone\) 。

因为 SAM 状态数是线性的，而每个节点最多只有常数个转移，所以转移数也是线性的，所以第一处和第二处是线性的。

我们接下来证明第三处也是线性的。

在每一次添加字符时我们不妨关注一下 \(shortest(link(last))\) ，在向 \(s\) 中添加字符之前，有 \(shortest(p)\le shortest(link(last))\) ，这是因为 \(link(last)\) 至多是 \(p\) ，我们由 \(q\) 拷贝得到了节点 \(clone\) ，并试图从 \(p\) 沿后缀链接上溯，将所有通往 \(q\) 的转移重定向为 \(clone\) ，这时 \(shortest(clone)\) 是严格变小的，加完字符后，我们有 \(last=cur\rightarrow link(last)=link(cur)=clone\) ，所以 \(shortest(link(last))\) 是在严格变小的，而且减小的幅度和改变转移的次数级别相同，故我们改变转移也是线性的。

可以在线构造后缀自动机的神奇网站

其他应用

对于一个字符串，把所有字符串加进 Trie 里面，然后进行压缩之后得到的树，是后缀树。后缀树上一条边代表的是一个字符串。对于一个串 \(s\)，我们建出反串的后缀自动机得到的 fail 树就是后缀树。

引用

• OIwiki

有一些明显的错误已经在本文改正。