算法课读书笔记之字符串算法学习体会及其应用-后缀自动机

后缀自动机——一种解决字符串问题的强力数据结构[^5]

后缀自动机的引入

后缀自动机(Suffix automaton, SAM)是IOI国家队成员陈立杰在2012年的冬令营从国外引进的一种数据结构, 它能在线性时间内解决许多字符串问题。
字符串的 SAM 可以理解为给定字符串的所有子串的压缩形式。值得注意的事实是，SAM 将所有的这些信息以高度压缩的形式储存。

SAM的定义

字符串 $s$ 的 SAM 是一个接受 $s$ 的所有后缀的最小 $DFA$ (确定性有限自动机或确定性有限状态自动机)。它能且只能接受所有 $S$ 的后缀, 并且拥有最少的状态与转移。

SAM的用途

考虑一个前置问题, 如果要在一个 $DAG$ (有向无环图) 上表示出一个字符串的所有子串, 我们可以怎么做? 最朴素的做法是建立一个 $Trie$ (字典树), 每一个节点都代表着子串的一个字符, 如下图，我们对字符串 $aabca$ 建立一个 $Trie$
图片说明
可以看到, 这种方法要表示出每一个后缀, 节点数是 $O(n^2)$ 的, 我们能不能通过状态压缩, 把一些多余的状态除去, 达到降低复杂度的目的呢? 这就是后缀自动机做的工作了!

SAM 的原理

我们先定义一个概念 $endpos(p)$ 表示一个子串 $p$ 在原串中出现的右端点,比如原串为 $aabab$ 子串 $ab$ 的 $endpos(ab)$ 为 ${3, 5}$ , 我们有以下几个结论:

两个子串的 $endpos$ 相同, 则其中一个必然为另一个的后缀
对于任意两个子串 $t$ 和 $p$ ( $len(t) <= len(p)$ ) 要么 $endpos(p) \in endpos(t)$ , 要么 $endpos(p) \cap endpos(t) = \varnothing$
对于 $endpos$ 相同的子串, 我们将它们归为一个等价类。对于任意一个等价类, 将包含在其中的子串从大到小排序, 则每一个子串的长度均为上一个子串的长度减 $1$ , 且为上一个子串的后缀
$endpos$ 等价类的个数级别为 $O(n)$
这一条结论是可以严格证明的。比如字符串 $abacaba$ 它有一个等价类包含 $aba$ 和 $ba$ , 对于一个等价类的最长子串 $p$ (如提到的 $aba$ ，如果我在这个 $p$ 开头任意添加一个字符, 显然它将不属于原来的等价类, 但是新得到的字符串的 $endpos$ 一定是原来 $endpos(p)$ 的子集, 但不等价, 否则与 等价类中 $\textbf{p}$ 是最长子串 这一事实矛盾。如果在前面添加的两个字符不相同, 那么这两个新串的 $endpos$ 必不相交。基于这个性质, 所有等价类都可以由一个原始状态通过分割得到, 但总的分割次数不会超过原来集合的大小, 因此最多可以分割的集合不超过 $\textbf{2n}$ , 由此证明等价类的数量级别为 $O(n)$
基于这个分割关系, 可以得到类之间的父子关系, 由此拓展出 $parent \ tree$ 的概念
如下图, 列出了字符串 $aababa$ 的 $parent \ tree$

特别的是, 我们要求的后缀自动机的节点跟 $parent \ tree$ 是一样的, 可以简单的理解为顺着后缀自动机的边走是在后面加字符, 而顺着 $parent \ tree$ 走是在前面加字符
对于一个等价类, 他的最长子串和最短子串长度分别记为 $len(p)$ 和 $minlen(p)$ , 对于他的父节点, 满足 $len(fa(p)) == minlen(p) + 1$
后缀自动的边集规模是 $O(n)$
证明: 对一个后缀自动机, 任取一个生成树, 然后从后缀自动机上的终止节点往回跑子串, 如果能顺利跑回源点, 则跑下个串, 否则连上本来要跑的边, 可以发现我们在这个过程中增加的边不会超过节点 $endpos$ 的大小, 这样, 当跑完终止节点, 原本生成树上增加的边数不会超过后缀数( $n$ ) 个, 因此, 总的边数规模为 $O(n)$
下面举一个例子, 图一是字符串 $abcd$ 的后缀自动机

后缀自动机的构造

后缀自动机的构造是在线的, 也就是一边插入一边构造, 动态地维护每一个节点的状态
具体的构造方法是运用了增量法
考虑我们当前以及拥有了前 $|S| - 1$ 个字符的后缀自动机, 且现在的自动机中的 $[1, |S| - 1]$ 位于状态 $last$ , 现在加入第 $|S|$ 个字符(假设该字符为 $c$ ), 那么会有一个新的状态 $np$ , 其中 $len_{np} = |S|$
此时后缀自动机上应该增加一个 $last \to np$ 的转移, 还应该加入一个 $fa_{last} \to np$ 的转移.....直到发现这个状态已经有一个字符 $c$ 的转移。不妨假设这个状态为 $p$ , 设它经过字符 $c$ 转移后状态为 $q$ 。
此时, $q$ 的等价类中会多出一个: 右端点为 $|S|$ 的串, 且最长的长度是 $len_p + 1$ , 出现以下两种情况:

$len_q = len_p + 1$ 。此时 $q$ 代表的所有串等价类仍然相同, 只需要令 $fa_{np} = q$ 即可
$len_q > len_p + 1$ 。此时 $q$ 代表的串中, 长度不超过 $len_p + 1$ 的串的等价类会多出一个值 $|S|$ , 而长度超过它的不会。为了维护一个状态中所有的串 $endpos$ 相同这一性质, 需要新建一个状态 $nq$ , $nq$ 代表原来串中所有长度不超过 $len_p + 1$ 的串, 因此 $len_nq = len_p + 1$ , nq 的其他属性( $fa$ 和转移)和原来的 $q$ 点一致。同时发现 $fa_q = fa_{np} = nq$ , 然后我们再次从 $p$ 开始, 本来 $p$ 的 $c$ 字符的转移是到点 $q$ ，现在应该转移到 $nq$ 。同理, 如果 $fa_p$ 的 $c$ 字符转移到的点是 $q$ , 那么它也应该转移到 $nq$ ..... 直到发现当前的 $c$ 字符转移到的不是 $q$ 为止, 此时我们便完成了后缀自动机的构造

struct SAM {
  int last, tot, sz[N << 1], len[N << 1], fa[N << 1];
  int ch[N << 1][30];

  SAM() {
    tot = 0, last = newNode(0), len[0] = -1;
    memset(sz, 0, sizeof sz);
  }
  inline int newNode(int v) {
    len[++tot] = v, fa[tot] = 0;
    memset(ch[tot], 0, sizeof ch[tot]);
    return tot;
  }
  void append(int c) {
    int p = last, u = newNode(len[last] + 1);
    sz[u] = 1;
    for (; p && !ch[p][c]; p = fa[p]) {
      ch[p][c] = u;
    }
    if (p == 0) { // 1是源点
      fa[u] = 1;
    } else { // len(q) == len(p) + 1 的情况
      int q = ch[p][c];
      if (len[q] == len[p] + 1) {
        fa[u] = q;
      } else { // // len(q) > len(p) + 1 的情况
        int nq = newNode(len[p] + 1);
        memcpy(ch[nq], ch[q], sizeof ch[q]);
        fa[nq] = fa[q], fa[u] = fa[q] = nq;
        for (; p && (ch[p][c] == q); p = fa[p]) {
          ch[p][c] = nq;
        }
      }
    }
    last = u;
  }
  void match(char *s) {
    int pos = 1, length = 0;
    for (int i = 0, n = strlen(s); i < n; i++) {
      while (pos && !ch[pos][s[i] - 'a']) {
        pos = fa[pos], length = len[pos];
      }
      if (pos) {
        ++length, pos = ch[pos][s[i] - 'a'];
        // update ans
      } else {
        pos = 1, length = 0;
      }
    }
  }
} sam;

后缀自动机的一些应用

求字符串的本质不同子串个数
根据后缀自动机的性质我们可以发现：
在后缀自动机上从根节点开始的每一条路径都是一个子串。
所以直接在 $SAM$ 上 $dfs$ 做 $dp$
有动态规划转移方程 $dp[u] = 1 + \sum\limits_{son}dp[v]$
时间复杂度 $O(n)$

ll dp[N];
bool vis[N];
void dfs(ll x) {
dp[x] = 1;
for(int i = 0; i < 26; i++) {
 int np = sam.ch[x][i];
 if(np && !vis[np]) {
   dfs(np);  
   vis[np] = 1; // 只搜一遍
 }
 dp[x] += dp[np]; // 做dp
}
}
char s[N];
int main() {
ios::sync_with_stdio(false), cin.tie(nullptr);
int n;
scanf("%d %s", &n, (s + 1));
for(int i = 1; i <= n; i++) {
 sam.append(s[i] - 'a'); // 插入后缀自动机
}
dfs(1); // 做深度优先遍历
cout << dp[1] - 1 << "\n"; // 因为源点是空的不算子串所以要减1
return 0;
}

求最长公共子串
具体思路是对于字符串 $s$ 和 $t$ , 先对 $s$ 建立后缀自动机, 然后对于 $t$ 从头遍历每个字符, 然后在后缀自动机上跑
对于当前的字符 $c$
如果当前节点有这个孩子，那么直接令 $len$ 加 1 即可。
如果没有就找一直向前找 $fa$ ，直到找到有 $c$ 这个孩子的节点。

char s[N], t[N];
int main() {
  ios::sync_with_stdio(false), cin.tie(nullptr);
  int n, m;
  int maxz = 0;
  int len = 0;
  cin >> (s + 1) >> (t + 1);
  n = strlen(s + 1), m = strlen(t + 1);
  for(int i = 1; i <= n; i++) {
    sam.append(s[i] - 'a'); // 插入
  }
  int p = 1;
  for(int i = 1; i <= m; i++) {
    int x = t[i] - 'a';
    if(sam.ch[p][x]) { // 有这个子节点 继续往下
      len++;
      p = sam.ch[p][x];
    } else { // 往上走
      while(p && !sam.ch[p][x]) p = sam.fa[p];
      if(!p) p = 1, len = 0;
      else len = sam.len[p] + 1, p = sam.ch[p][x];
    }
    maxz = max(maxz, len);
  }
  cout << maxz << "\n";
  return 0;
}

总结

关于后缀自动机还有很多其他的用途, 比如字典序 $k$ 小子串, 字典序最小后缀等等, 这里提到的只是很简单基础的一部分。虽然在大多数工程的领域上后缀自动机的应用比较少, 但是在算法竞赛和高性能计算领域对后缀自动机的掌握提出了比较高的要求, 通过学习后缀自动机, 理解它的思想, 对我们研究更高性能的算法有重要意义。

参考文献

[^5]: 参考国家集训队2015论文集张天扬 <<后缀自动机及其应用>>