跳转至

后缀自动机 (SAM)

一些前置约定/定义

记 \Sigma为字符集，\left|\Sigma\right|为字符集大小。 对于一个字符串 s，记 \left|s\right|为其长度。

后缀自动机概述

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

举个例子，以下的字符串问题都可以在线性时间内通过 SAM 解决。

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

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

SAM 的定义

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

换句话说：

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

子串的性质

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

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

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

构造 SAM

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

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

对于字符串 s=“"：

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

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

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

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

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

在线性时间内构造 SAM

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

结束位置 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集合被分为若干 等价类 。

显然， SAM 中的每个状态对应一个或多个 endpos相同的子串。换句话说， SAM 中的状态数等于所有子串的等价类的个数，再加上初始状态。 SAM 的状态个数等价于 endpos相同的一个或多个子串所组成的集合的个数 +1​。

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

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

引理 1： 两个非空子串 u和 w（假设 \left|u\right|\le \left|w\right|）的 endpos相同，当且仅当字符串 u是 w的后缀。

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

引理 2： 考虑两个非空子串 u和 w（假设 \left|u\right|\le \left|w\right|）。那么要么 endpos(u)\cap endpos(w)=\varnothing，要么 endpos(w)\subseteq endpos(u)，取决于 u是否为 w的一个后缀：

\begin{cases} endpos(w) \subseteq endpos(u) & \text{if } u \text{ is a suffix of } w \\ endpos(w) \cap endpos(u) = \varnothing & \text{otherwise} \end{cases}

证明：如果集合 endpos(u)与 endpos(w)有至少一个公共元素，那么由于字符串 u与 w在相同位置结束， u是 w的一个后缀。所以在每次 w出现的位置，子串 u也会出现。所以 endpos(w)\subseteq endpos(u)。

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

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

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

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

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

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

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

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

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

证明：考虑任意不是 t_0的状态 v，后缀链接 link(v)连接到的状态对应于严格更短的字符串（后缀链接的定义、引理 3）。因此，沿后缀链接移动，我们总是能到达对应空串的初始状态 t_0。

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

证明：由引理 2，任意一个 SAM 的 endpos集合形成了一棵树（因为两个集合要么完全没有交集要么其中一个是另一个的子集）。

我们现在考虑任意不是 t_0的状态 v及后缀链接 link(v)，由后缀链接和引理 2，我们可以得到

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

结合前面的引理有：后缀链接构成的树本质上是 endpos集合构成的一棵树。

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

小结

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

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

算法

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

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

一开始 SAM 只包含一个状态 t_0，编号为 0（其它状态的编号为 1,2,\ldots）。为了方便，对于状态 t_0我们指定 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构造完完整的 SAM 后找到所有的终止状态。为此，我们从对应整个字符串的状态（存储在变量 last中），遍历它的后缀链接，直到到达初始状态。我们将所有遍历到的节点都标记为终止节点。容易理解这样做我们会准确地标记字符串 s的所有后缀，这些状态都是终止状态。

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

因为我们只为 s的每个字符创建一个或两个新状态，所以 SAM 只包含 线性个 状态。

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

正确性证明

  • 若一个转移 (p,q)满足 len(p)+1=len(q)，则我们称这个转移是 连续的 。否则，即当 len(p)+1<len(q)时，这个转移被称为 不连续的 。从算法描述中可以看出，连续的、不连续的转移是算法的不同情况。连续的转移是固定的，我们不会再改变了。与此相反，当向字符串中插入一个新的字符时，不连续的转移可能会改变（转移边的端点可能会改变）。
  • 为了避免引起歧义，我们记向 SAM 中插入当前字符 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的一个转移。

对操作次数为线性的证明

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

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

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

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

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

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

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

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

实现

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

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

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

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

我们定义一个函数来初始化 SAM （创建一个只有初始状态的 SAM）。

1
2
3
4
5
6
void sam_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 sam_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(n\left|\Sigma\right|)，其中 \left|\Sigma\right|为字符集大小），你可以在 O(n)的时间内构造字符集大小任意的 SAM。但是这样你需要为每一个状态储存一个大小为 \left|\Sigma\right|的数组（用于快速跳转到转移的字符），和另外一个所有转移的链表（用于快速在转移中迭代）。

更多性质

状态数

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

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

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

字符串 “abbb\ldots bbb\!"的状态数达到了该上界：从第三次迭代后的每次迭代，算法都会拆开一个状态，最终产生恰好 2n-1个状态。

转移数

对于一个长度为 n的字符串 s，它的 SAM 中的转移数 不会超过 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。

因此我们可以获得更为紧确的 SAM 的转移数的上界： 3n-4。字符串 “abbb\ldots bbbc\!"就达到了这个上界。

应用

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

检查字符串是否出现

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

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

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

不同子串个数

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

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

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

考虑到 SAM 为有向无环图，不同路径的条数可以通过动态规划计算。即令 d_{v}为从状态 v开始的路径数量（包括长度为零的路径），则我们有如下递推方程：

d_{v}=1+\sum_{w:(v,w,c)\in DAWG}d_{w}

即， d_{v}可以表示为所有 v的转移的末端的和。

所以不同子串的个数为 d_{t_0}-1（因为要去掉空子串）。

总时间复杂度为： O(\left|S\right|)。

所有不同子串的总长度

给定一个字符串 S，计算所有不同子串的总长度。

本题做法与上一题类似，只是现在我们需要考虑分两部分进行动态规划：不同子串的数量 d_{v}和它们的总长度 ans_{v}。

我们已经在上一题中介绍了如何计算 d_{v}。 ans_{v}的值可以通过以下递推式计算：

ans_{v}=\sum_{w:(v,w,c)\in DAWG}d_{w}+ans_{w}