跳转至

后缀自动机 (SAM)

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

举个例子，字符串问题：

  • 在另一个字符串中搜索一个字符串的所有出现位置。
  • 计算给定的字符串中有多少个不同的子串。

以上问题都可以在线性的时间复杂度内通过后缀自动机来实现。

直观上，字符串的后缀自动机可以理解为给定字符串的所有子串的压缩形式。值得注意的事实是，后缀自动机将所有的这些信息以高度压缩的形式储存。对于一个长度为 n 的字符串，它的空间复杂度仅为 O(n) 。此外，构造后缀自动机的时间复杂度仅为 O(n) （这里我们将字符集的大小 k 看作常数，否则时间复杂度和空间复杂度均为 O(n\log k) ）。

后缀自动机的定义

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

换句话说：

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

子串的性质

后缀自动机最简单和最重要的性质是，它包含关于字符串 s 的所有子串的信息。任意从初始状态 t_0 开始的路径，如果我们将转移路径上的标号写下来，都会形成 s 的一个子串。反之每个 s 的子串对应于从 t_0 开始的某条路径。

为了简化表达，我们将会说子串对应于一条路径（从 t_0 开始且一些标号构成这个子串）。反过来我们说任意一条路径对应于它的标号构成的字符串。

一条或多条路径可以到达一个状态，因此我们说一个状态对应于字符串的集合，这也对应于那些路径。

构造后缀自动机的实例

我们将会在这里展示一些简单的字符串的后缀自动机。

我们用蓝色表示初始状态，用绿色表示终止状态。

对于字符串 s=``" ：

对于字符串 s=``a\!" ：

对于字符串 s=``aa\!" ：

对于字符串 s=``ab\!" ：

对于字符串 s=``abb\!" ：

对于字符串 s=``abbb\!" ：

在线性时间内构造后缀自动机

在我们描述线性时间内构造后缀自动机的算法之前，我们需要引入几个对理解构造过程非常重要的新概念并简单证明。

结束位置 endpos

考虑字符串 s 的任意非空子串 t ，我们记 endpos(t) 为在字符串 s 中 t 的所有结束位置（假设对字符串中字符的编号从零开始）。例如，对于字符串 ``abcbc\!" ，我们有 endpos(``bc\!")=2,\,4 。

当两个子串 t_1 与 t_2 的末尾集合相等时我们称它们是 endpos 等价的：即 endpos(t_1)=endpos(t_2) 。这样所有字符串 s 的非空子串都可以根据它们的 endpos 集合被分为几个等价类。

显然，在后缀自动机中的每个状态对应于一个或多个 endpos 相同的子串。换句话说，后缀自动机中的状态数等于所有子串的等价类的个数，加上初始状态。后缀自动机的状态个数等价于 endpos 相同的一个或多个子串。

我们稍后将会用这个假设介绍构造后缀自动机的算法。在那时我们将会发现，后缀自动机需要满足的所有性质，除了最小性以外都满足了。由 Nerode 定理我们可以得出最小性（这篇文章不会证明后缀自动机的最小性）。

由 endpos 的值我们可以得到一些重要结论：

引理 1：当且仅当字符串 u 以 w 的一个后缀的形式出现在字符串 s 中时，两个非空子串 u 和 w （假设 length(u)\le length(w) ）是 endpos 等价的。

引理显然成立。如果 u 和 v 的 endpos 相同，则 u 是 w 的一个后缀，且只以 s 中的一个 w 的后缀的形式出现。且根据定义，如果 u 为 w 的一个后缀，且只以后缀的形式在 s 中出现时，两个子串的 endpos 值相等。

引理 2：考虑两个非空子串 u 和 w （假设 length(u)\le length(w) ）。则它们的 endpos 构成的集合要么完全没有交集，要么 endpos(w) 是 endpos(u) 的一个子集。并且这依赖于 u 是否为 w 的一个后缀。即：

\begin{cases} endpos(w)\subseteq endpos(u)&\text{若 $u$ 为 $w$ 的一个后缀}\\ endpos(w)\cap endpos(u)=\emptyset&\text{另一种情况}\\ \end{cases}

证明：如果集合 endpos(u) 与 endpos(w) 有至少一个公共元素，那么由于字符串 u 与 w 都在一个位置结束，即 u 是 w 的一个后缀。但是如果如此在每次 w 出现的位置子串 u 也会出现，这意味着 endpos(w) 是 endpos(u) 的一个子集。

引理 3：考虑一个 endpos 等价类。将类中的所有子串按长度非递增的顺序排序。即每个子串都会比它前一个子串短，与此同时每个子串也是它前一个子串的一个后缀。换句话说，同一等价类中的所有子串均互为后缀，且子串的长度恰好覆盖整个区间 [x,\,y] 。

证明：固定一些 endpos 等价类。如果等价类中只包含一个子串，引理显然成立。现在我们来讨论子串元素个数大于 1 的等价类。

由引理 1，两个不同的 endpos 等价字符串中较短的一个总是较长的一个的真后缀。因此，等价类中不可能有两个等长的字符串。

记 w 为等价类中最长的字符串，类似地，记 u 为等价类中最短的字符串。由引理 1，字符串 u 是字符串 w 的真后缀。现在考虑长度在区间 [length(u),\,length(w)] 中的 w 的任意后缀。容易看出，这个后缀也在同一等价类中。因为这个后缀只能在字符串 s 中以 w 的一个后缀的形式存在（也因为较短的后缀 u 在 s 中只以 w 的后缀的形式存在）。因此，由引理 1，这个后缀与字符串 w endpos 等价。

考虑后缀自动机中满足 v\ne t_0 的一些状态。我们已经知道，状态 v 对应于具有相同 endpos 的等价类。我们如果定义 w 为这些字符串中最长的一个，则所有其它的字符串都是 w 的后缀。

我们还知道字符串 w 的前几个后缀（如果我们用长度降序考虑这些后缀）在这个等价类中全部被包含，且所有其它后缀（至少一个—空后缀）在其它的等价类中。我们记 t 为最大的这样的后缀，然后用后缀链接连到 t 上。

换句话说，一个后缀链接 link(v) 连接到对应于 w 的最长后缀的另一个 endpos 等价类的状态。

以下我们假设初始状态 t_0 对应于它自己这个等价类（只包含一个空字符串），为了方便我们规定 endpos(t)=\{-1,\,0,\,\ldots,\,length(s)-1\} 。

引理 4：所有后缀链接构成一棵根节点为 t_0 的树。

证明：考虑任意满足 v\ne t_0 的状态，一个后缀链接 link(v) 连接到的状态对应于严格更短的字符串（根据后缀链接的定义和引理 3）。因此，通过在后缀链接上移动，我们早晚会到达对应空串的初始状态 t_0 。

引理 5：如果我们使用集合 endpos 构造一棵树（所有子节点的集合为父节点的子集），则这个结构由后缀链接连接起来。

证明：由引理 2，我们可以用 endpos 集合构造一棵树（因为两个集合要么完全没有交集要么互为子集）。

我们现在考虑任意满足 v\ne t_0 的状态和它的后缀链接 link(v) ，由后缀链接和引理 2，我们可以得到

endpos(v)\subseteq endpos(link(v))

，这与前面的引理证明了以下断言成立：后缀链接构成的树本质上是 endpos 集合构成的一棵树。

以下是对于字符串 ``abcbc\!" 构造后缀自动机时产生的后缀链接树的一个例子，节点被标记为对应等价类中最长的子串。

小结

在学习算法本身前，我们对之前学过的知识进行一下总结，并引入一些辅助记号。

  • s 的子串可以根据它们结束的位置 endpos 被划分为多个等价类；
  • 后缀自动机由初始状态 t_0 和与每一个 endpos 等价类对应的每个状态组成；
  • 对于每一个状态 v ，一个或多个子串与之匹配。我们记 longest(v) 为其中最长的一个字符串，记 len(v) 为它的长度。类似地，记 shortest(v) 为最短的子串，它的长度为 minlen(v) 。那么所有对应这个状态的所有字符串都是字符串 longest(v) 的不同的后缀，且所有字符串的长度恰好覆盖区间 [minlength(v),\,len(v)] 中的每一个整数。
  • 对于任意满足 v\ne t_0 的状态，定义后缀链接为连接到对应字符串 longest(v) 的长度为 minlen(v)-1 的后缀的一条边。从根节点 t_0 出发的后缀链接可以形成一棵树，与此同时，这棵树形成了 endpos 集合间的包含关系。
  • 我们可以对 v\ne t_0 的状态使用后缀链接 link(v) 解释 minlen(v) 如下：
minlen(v)=len(link(v))+1.
  • 如果我们从任意状态 v_0 开始顺着后缀链接遍历，早晚都会到达初始状态 t_0 。这种情况下我们可以得到一个互不相交的区间 [minlen(v_i),\,len(v_i)] 的序列，且它们的并集形成了连续的区间 [0,\,len(v_0)] 。

算法

现在我们可以学习算法本身了。这个算法是在线算法，这意味着我们可以逐个加入字符串中的每个字符，并且在每一步中对应地维护后缀自动机。

为了保证线性的空间复杂度，我们将只保存 len 和 link 的值和每个状态的一个转移列表，我们不会标记终止状态（但是我们稍后会展示在构造后缀自动机后如何分配这些标记）。

一开始后缀自动机只包含一个状态 t_0 ，编号为 0 （其它状态的编号为 1,\,2,\,\ldots ）。为了方便，我们分配给它 len=0 和 link=-1 （ -1 表示一个虚拟的不存在的状态）。

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

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

如果我们还想知道哪些状态是终止状态而哪些不是，我们可以在为字符串 s 构造完完整的后缀自动机后找到所有的终止状态。为此，我们从对应整个字符串的状态（存储在变量 last 中），遍历它的后缀链接，直到到达初始状态。我们将所有遍历到的节点都标记为终止节点。容易理解这样做我们会精确地标记字符串 s 的所有后缀，这些状态恰好是终止状态。

在下一部分，我们将观察算法每一步的细节，并证明它的正确性。

现在，我们只注意到，因为我们只为 s 的每个字符创建一个或两个新状态所以后缀自动机只包含线性个状态。

转移个数是线性规模的，以及总体上算法的运行时间是线性规模的，这两点还不那么清 楚。

正确性证明

  • 若一个转移 (p,\,q) 满足 len(p)+1=len(q) 则我们称这个转移是连续的。否则，即当 len(p)+1<len(q) 时，这个转移被称为不连续的。 从算法描述中可以看出，连续的和非连续的转移是算法的不同情况。连续的转移是固定的，我们不会再改变了。与此相反，当向字符串中插入一个新的字符时，非连续的转移可能会改变（转移边的端点可能会改变）。
  • 为了避免引起歧义，我们记向后缀自动机中插入当前字符 c 之前的字符串为 s 。
  • 算法从创建一个新状态 cur 开始，对应于整个字符串 s+c 。我们创建一个新的节点的原因很清楚。与此同时我们也创建了一个新的字符和一个新的等价类。
  • 在创建一个新的状态之后，我们会从对应于整个字符串 s 的状态通过后缀链接进行遍历。对于每一个状态，我们尝试添加一个从字符 c 到新状态 cur 的转移。然而我我们只能添加与原来已存在的转移不冲突的转移。因此我们只要找到已存在的 c 的转移，我们就必须停止。
  • 最简单的情况是我们到达了虚拟状态 -1 ，这意味着我们为所有 s 的后缀添加了 c 的转移。这也意味着，字符 c 从未在字符串 s 中出现过。因此 cur 的后缀链接为状态 0 。
  • 第二种情况下，我们找到了现有的转移 (p,\,q) 。这意味着我们尝试向自动机内添加一个已经存在的字符串 x+c （其中 x 为 s 的一个后缀，且字符串 x+c 已经作为 s 的一个子串出现过了）。因为我们假设字符串 s 的自动机的构造是正确的，我们不应该在这里添加一个新的转移。 然而，有一个难点。从状态 cur 出发的后缀链接应该连接到哪个状态呢？我们要把后缀链接连到一个状态上，且其中最长的一个字符串恰好是 x+c ，即这个状态的 len 应该是 len(p)+1 。然而还不存在这样的状态，即 len(q)>len(p)+1 。这种情况下，我们必须要通过拆开状态 q 来创建一个这样的状态。
  • 如果转移 (p,\,q) 是连续的，那么 len(q)=len(p)+1 。在这种情况下一切都很简单。我们只需要将 cur 的后缀链接指向状态 q 。
  • 否则转移是不连续的，即 len(q)>len(p)+1 ，这意味着状态 q 不只对应于长度为 len(p)+1 的后缀 s+c ，还对应于 s 的更长的子串。除了将状态 q 拆成两个子状态以外我们别无他法，所以第一个子状态的长度就是 len(p)+1 了。
    我们如何拆开一个状态呢？我们复制状态 q ，产生一个状态 clone ，我们将 len(clone) 赋值为 len(p)+1 。由于我们不想改变遍历到 q 的路径，我们将 q 的所有转移复制到 clone 。我们也将从 clone 出发的后缀链接设置为 q 的后缀链接的目标，并设置 q 的后缀链接为 clone 。
    在拆开状态后，我们将从 cur 出发的后缀链接设置为 clone 。
    最后一步我们将一些到 q 转移重定向到 clone 。我们需要修改哪些转移呢？只重定向相当于所有字符串 w+c （其中 w 是 p 的最长字符串）的后缀就够了。即，我们需要继续沿着后缀链接遍历，从顶点 p 直到虚拟状态 -1 或者是转移到不是状态 q 的一个转移。

对操作次数为线性的证明

首先我们假设字符集大小为常数。如果字符集大小不是常数，后缀自动机的时间复杂度就不是线性的。从一个顶点出发的转移存储在支持快速查询和插入的平衡树中。因此如果我们记 k 为字符集的大小，则算法的渐进时间复杂度为 O(n\log k) ，空间复杂度为 O(n) 。然而如果字符集足够小，可以不写平衡树，以空间换时间将每个顶点的转移存储为长度为 k 的数组（用于快速查询）和链表（用于快速遍历所有可用关键字）。这样算法的时间复杂度为 O(n) ，空间复杂度为 O(nk) 。

所以我们将认为字符集的大小为常数，即每次对一个字符搜索转移、添加转移、查找下一个转移—这些操作的时间复杂度都为 O(1) 。

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

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

我们使用后缀自动机的大小（状态数和转移数）为线性的的事实（对状态数是线性的的证明就是算法本身，对状态数为线性的的证明将在稍后实现算法后给出）。

因此上述第一处和第二处的总复杂度显然为线性的，因为单次操作均摊只为自动机添加了一个新转移。

还需为第三处估计总复杂度，我们将最初指向 q 的转移重定向到 clone 。我们记 v=longest(p) ，这是一个字符串 s 的后缀，每次迭代长度都递减—因为作为字符串 s 的位置随着每次迭代都单调上升。这种情况下，如果在循环的第一次迭代之前，相对应的字符串 v 在距离 last 的深度为 k (k\ge2) 的位置上（深度记为后缀链接的数量），那么在最后一次迭代后，字符串 v+c 将会成为路径上第二个从 cur 出发的后缀链接（它将会成为新的 last 的值）。

因此，循环中的每次迭代都会使作为当前字符串的后缀的字符串 longest(link(link(last)) 的位置单调递增。因此这个循环最多不会执行超过 n 次迭代，这正是我们需要证明的。

实现

首先，我们描述一种存储一个转移的全部信息的数据结构。如果需要的话，你可以在这里加入一个终止标记，也可以是一些其它信息。我们将会用一个 map 存储转移的列表，允许我们在总计 O(n) 的空间复杂度和 O(n\log k) 的时间复杂度内处理整个字符串。

1
2
3
4
struct state {
  int len, link;
  map<char, int> next;
};

后缀自动机本身将会存储在一个 state 结构体数组中。我们记录当前自动机的大小 sz 和变量 last，当前整个字符串对应的状态。

1
2
3
const int MAXLEN = 100000;
state st[MAXLEN * 2];
int sz, last;

我们定义一个函数来初始化后缀自动机（创建一个只有一个状态的后缀自动机）。

1
2
3
4
5
6
void sa_init() {
  st[0].len = 0;
  st[0].link = -1;
  sz++;
  last = 0;
}

最终我们给出主函数的实现—给当前行末增加一个字符，对应地重建自动机。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
void sa_extend(char c) {
  int cur = sz++;
  st[cur].len = st[last].len + 1;
  int p = last;
  while (p != -1 && !st[p].next.count(c)) {
    st[p].next[c] = cur;
    p = st[p].link;
  }
  if (p == -1) {
    st[cur].link = 0;
  } else {
    int q = st[p].next[c];
    if (st[p].len + 1 == st[q].len) {
      st[cur].link = q;
    } else {
      int clone = sz++;
      st[clone].len = st[p].len + 1;
      st[clone].next = st[q].next;
      st[clone].link = st[q].link;
      while (p != -1 && st[p].next[c] == q) {
        st[p].next[c] = clone;
        p = st[p].link;
      }
      st[q].link = st[cur].link = clone;
    }
  }
  last = cur;
}

正如之前提到的一样，如果你用内存换时间（空间复杂度为 O(nk) ，其中 k 为字符集大小），你可以在 O(n) 的时间内构造字符集大小 k 任意的后缀自动机。但是这样你需要为每一个状态储存一个大小为 k 的数组（用于快速跳转到转移的字符），和另外一个所有转移的链表（用于快速在转移中迭代）。

更多的性质

状态数

对于一个长度为 n 的字符串 s ，它的后缀自动机中的状态数不会超过 2n-1 （假设 n\ge2 ）。

对上述结论的证明就是算法本身，因为一开始自动机含有一个状态，第一次和第二次迭代中只会创建一个节点，剩余的 n-2 步中每步会创建至多 2 个状态。

然而我们也能在不知道这个算法的情况下展示这个估计值。我们回忆一下状态数等于不同的 endpos 集合个数。另外这些 endpos 集合形成了一棵树（祖先节点的集合包含了它所有孩子节点的集合）。考虑将这棵树稍微变形一下：只要它有一个只有一个孩子的内部顶点（这意味着该子节点的集合至少遗漏了它的父集合中的一个位置），我们创建一个含有这个遗漏位置的集合。最后我们可以获得一棵每一个内部顶点的度数大于一的树，并且叶子节点的个数不超过 n 。因此这样的树里有不超过 2n-1 个节点。

对于每个确定的 n ，状态数的上界是确定的。一个可能的字符串是：

``abbb\ldots bbb\!"

从第三次迭代后的每次迭代，算法都会拆开一个状态，最终产生恰好 2n-1 个状态。

转移数

对于一个长度为 n 的字符串 s ，它的后缀自动机中的转移数不会超过 3n-4 （假设 n\ge 3 ）。

证明如下：

我们首先估计连续的转移的数量。考虑自动机中从状态 t_0 开始的最长路径的生成树。生成树的骨架只包含连续的边，因此数量少于状态数，即，边数不会超过 2n-2 。

现在我们来估计非连续的转移的数量。令当前非连续转移为 (p,\,q) ，其字符为 c 。我们取它的对应字符串 u+c+w ，其中字符串 u 对应于初始状态到 p 的最长路径， w 对应于从 p 到任意终止状态的最长路径。一方面，对于每个不完整的字符串所对应的形如 u+c+w 的字符串是不同的（因为字符串 u 和 w 仅由完整的转移组成）。另一方面，由终止状态的定义，每个形如 u+c+w 的字符串都是整个字符串 s 的后缀。因为 s 只有 n 个非空后缀，且形如 u+c+w 的字符串都不包含 s （因为整个字符串只包含完整的转移），所以非完整的转移的总数不会超过 n-1 。

将以上两个估计值结合起来，我们可以得到上界 3n-3 。然而，最大的状态数只能在测试数据 ``abbb\ldots bbb\!" 中产生，这个测试数据的转移数量显然少于 3n-3 ，我们可以获得更为紧确的后缀自动机的转移数的上界： 3n-4 。

上界可以通过字符串

``abbb\ldots bbbc\!"

达到。

应用

下面我们来看一下一些可以用后缀自动机解决的问题。为了简单，我们假设字符集的大小 k 为常数，允许我们认为增加一个字符和遍历的复杂度为常数。

检查字符串是否出现

给一个文本串 T 和多个模式串 P ，我们要检查字符串 P 是否作为 T 的一个子串出现。

我们在 O(length(T)) 的时间内为文本串 T 构造后缀自动机。为了检查模式串 T 是否在 T 中出现，我们沿转移（边）从 t_0 开始根据 P 的字符进行转移。如果在某个点无法转移下去，则模式串 P 不是 T 的一个子串。如果我们能够这样处理完整个字符串 P ，那么模式串在 T 中出现过。因此

对于每个字符串 P 算法的时间复杂度为 O(length(P)) 。此外，这个算法还找到了模式串 P 在文本串中出现的最大前缀长度。

不同子串个数

给一个字符串 S ，计算不同子串的个数。

为字符串 S 构造后缀自动机。

每个 S 的子串都相当于自动机中的一些路径。因此不同子串的个数等于自动机中以 t_0 为起点的不同路径的条数。

考虑到后缀自动机为有向无环图，不同路径的条数可以使用动态规划计算。

即，令 d[v] 为从状态 v 开始的路径数量（包括长度为零的路径），则我们有如下递推方程式：

d[v]=1+\sum_{w:(v,\,w,\,c)\in SA}d[w]