后缀自动机(Suffix Automaton) · Leager / Field Notes

翻阅网络资料两天后顿悟，遂写下心得。

参考资料
OI Wiki
知乎。并贴心地给出了构建过程的中间形态

性质

关于**后缀自动机(SAM)**的所有概念，其实网上说的都已经差不多了。个人总结出以下几个关键的性质：

在 SAM 中，能够通过一个状态(State)来表示一组 endpos 相同的字符串，并且有一个起始 State（$Start$）来表示空字符串；
所谓 endpos 其实就是字符串在「源串」（下面简称 src）中所有结束位置的集合。比如字符串 "aabab" 中 "ab" 的 endpos 就是 {2, 4}
SAM 可以表示为一个树形结构，并且树上的所有节点都是一个 State，且根节点对应 $Start$；
如果将一个 State 表示的所有字符串以降序排序，假设得到的结果是 ${s_1, s_2, \dots, s_n}$，那么对于任意 $i<j$，有 $s_j$ 是 $s_i$ 的真后缀，并且 $len(s_{i-1}) = len(s_i) - 1$；
在上面的例子中，"ab" 和 "b" 属于同一 State（它们的 endpos 都是 {2, 4}），这两个字符串满足上述性质。为此，需要在 State 中维护一个 length 变量，意为 State 表示的所有字符串中的最大长度。
对于某一 State $A$ 在树中的所有祖先 State $B$，可以得出 $B$ 表示的所有字符串 $b_i$ 都是 $A$ 中所有字符串 $a_i$ 的真后缀，同时 $endpos_A \subseteq endpos_B$；
为此，需要在 State 中维护一个 parent 变量，以转移到父 State。通常这一步也叫「后缀压缩」。
State 还需要能够通过某一字符 ch 转移到另一 State（如果存在这样一种转移的话），并且认为 State $A$ 表示的所有字符串 $a_i$ 在添加字符 ch 后的所有新字符串 $a_i’$ 是 $b_i$ 的后缀；
为此，需要在 State 中维护一个 next 变量，通常是一个 unordered map<char, int>。当然如果字符集只有小写字母，也可以直接用一个长度为 26 的数组。

构建

基于以上性质，其实不难理解 SAM 的构建代码了。因为这是一个 online 结构，我们可以随时添加新字符/字符串以更新自动机。每次新增一个字符 ch，相当于建立了一个新的 State $New$（此刻仅表示添加了 ch 后的新串 newStr，对应 endpos 为 $len(newStr)-1$）。

接下去这句个人理解我认为很关键：添加 $New$ 后重构 SAM 的过程，本质上就是找一个合适的 State 作为 $New$ 的 parent 的过程。

根据性质 4，这个所谓的合适的 State，其表示的所有字符串必须能作为 newStr 的后缀，且最长串应尽可能长。

如果我们能够把上一次添加字符所构建的 State $Last$ 考虑进来，问题就会变得很简单——$Last$ 所表示的字符串（暂且称为 oldStr 好了）在添加了 ch 后恰好就是 newStr 的后缀。

那么只需要遍历 $Last$ 的所有祖先即可。因为如果一个 State 不是 $Last$ 的祖先，其表示的字符串也不会是 $Last$ 所表示字符串的后缀，也就无法在添加 ch 后成为 newStr 的后缀了。这也是板子的前半段代码的基本思想。对于上述 States，需要在 next 中添加到 $New$ 的转移。

 1// 新建状态
 2automaton.emplace_back(++strLength_, 0);
 3State& newState = automaton.back();
 4stateIndex newStateIdx = automaton.size() - 1;
 5
 6stateIndex p;
 7for (p = last_; p != NIL && !automaton[p].next.count(ch); p = automaton[p].parent) {
 8  // 遍历 last 的祖先，添加转移
 9  automaton[p].next[ch] = newStateIdx;
10}

如果直接遍历完在 $Start$ 的 parent 处停止，意味着 ch 没有在 oldStr 中出现过，可用反证法证明之。

那么如果遇到某个 State $P$（包括 $Start$），其已经能通过 ch 转移到其他 State $Q$ 了，说明 ch 肯定在 oldStr 中出现过。

由于此时此刻集合 endpos($New$) 的大小为 1，那么对于 oldStr 的所有后缀 $old_i$，如果子串 $old_i + ch$ 未在 oldStr 中出现过，那其必定与 newStr 对应同一 endpos 集合。否则，就像之前说的那样，$old_i$ 所属的 State $P$ 存在一个到另一 State $Q$ 的转移。

这需要分情况讨论，其实也就是所有资料都提到的两种情况：

$len(P) + 1 = len(Q)$
$len(P) + 1 < len(Q)$

对于第一种情况，表明 $Q$ 就是我们要找的 parent。因为此时不存在一个 State 能够表示更长且与 newStr 的 endpos 不同的字符串了。

1if (automaton[p].length + 1 == automaton[q].length) {
2  newState.parent = q;
3}

对于第二种情况，表明虽然 $Q$ 表示的最长串不一定是 newStr 的后缀，但 $old_i + ch$ 一定是，并且根据性质 5，$old_i + ch$ 必定能作为 $Q$ 表示的所有字符串的后缀。此时 $New$ 和 $Q$ 有了一个公共后缀 $old_i + ch$，并且此时 endpos($old_i + ch$) 就会与 endpos($Q$) 产生差异——多了一项 $len(newStr)-1$。

于是就又产生了一个新的 State，并且这个新的 State 是基于 $Q$ 的——对于 $P$ 及其所有祖先，一旦能够通过 ch 转移到 $Q$，那就必然能够转移到这个新的 State；同时又能继承 $Q$ 的所有转移（这很显然，毕竟是 $Q$ 的后缀）。所以一般把这个 State 称为 $Clone$。

 1else {
 2  automaton.emplace_back(automaton[q]);
 3  State& cloneState = automaton.back();
 4  stateIndex cloneStateIdx = automaton.size() - 1;
 5  cloneState.length = automaton[p].length + 1; // 别忘了修改 length
 6
 7  // 修改 p 的祖先中所有转移到 q 的 State
 8  for (; p != NIL; p = automaton[p].parent) {
 9    auto iter = automaton[p].next.find(ch);
10    if (iter == automaton[p].next.end() || iter->second != q) {
11      break;
12    }
13    iter->second = cloneStateIdx;
14  }
15
16  // 最后 New 和 Q 都指向 Clone
17  automaton[q].parent = cloneStateIdx;
18  newState.parent = cloneStateIdx;
19}

最后的最后，还要修改 $Last$ 使其指向 $New$。到这就大功告成了。完整实现如下：

 1void SuffixAutomaton::insert(char ch) {
 2  automaton.emplace_back(++strLength_, 0);
 3  State& newState = automaton.back();
 4  stateIndex newStateIdx = automaton.size() - 1;
 5
 6  stateIndex p;
 7  for (p = last_; p != NIL && !automaton[p].next.count(ch); p = automaton[p].parent) {
 8    automaton[p].next[ch] = newStateIdx;
 9  }
10
11  if (p != NIL) {  //  {p} + c is a suffix of {q}
12    stateIndex q = automaton[p].next[ch];
13    if (automaton[p].length + 1 == automaton[q].length) {
14      // endpoint({p} + c) change in sync with endpoint({q})
15      newState.parent = q;
16    } else {
17      // size(endpoint({p} + c)) > size(endpoint({q})), so we should
18      // create a new intermidiate state "cloneState" to present {p} + c
19      automaton.emplace_back(automaton[q]);
20      State& cloneState = automaton.back();
21      stateIndex cloneStateIdx = automaton.size() - 1;
22      cloneState.length = automaton[p].length + 1;
23      cloneState.firstTime =
24          automaton[q].firstTime + automaton[q].length - cloneState.length;
25
26      for (; p != NIL; p = automaton[p].parent) {
27        auto iter = automaton[p].next.find(ch);
28        if (iter == automaton[p].next.end() || iter->second != q) {
29          break;
30        }
31        iter->second = cloneStateIdx;
32      }
33
34      automaton[q].parent = cloneStateIdx;
35      newState.parent = cloneStateIdx;
36    }
37  }
38
39  for (p = automaton[newStateIdx].parent; p != NIL; p = automaton[p].parent) {
40    automaton[p].cnt++;
41  }
42
43  last_ = newStateIdx;
44}

应用

SAM 是处理字符串问题的利器，根据前文提到的几条性质，其实可以实现包括但不限于以下功能：

判断模式串是否匹配；
不同子串数；
模式串的出现次数；
查找模式串的首个出现位置；
最长公共子串；
…

所有的实现代码放在了仓库中。只能说，理解 parent 和 next 很关键。

性质

构建

应用

线段树

树状数组