【Coel.学习笔记】后缀自动机

来了！NOI 算法中最抽象的字符串算法——后缀自动机！
当然咱只是一个普通的小 OIer，不会搞那么多杂七杂八的ww

引入

后缀自动机（\(\text{Suffix Automaton}\)，简称 \(\text{SAM}\)）是一种确定性有限状态自动机（\(\text{Determined Finite Automaton}\)，简称 \(\text{DFA}\)），通过把一个字符串的所有子串存储到一张有向无环图上，并借助图上的状态转移在线性时间内实现字符串的各种操作。

各种定义与性质

SAM 有点过于枯燥（emm），所以直接讲各种定义性质了，先不看例题~
取一张网上的图片作为例子。

性质一：子串对应性

在 SAM 上，所有从起点开始的路径能够与原字符串的子串一一对应，并且 SAM 的边数为 \(O(n)\) 级别。

性质二：节点包含性

每个节点可以对应若干个子串。每个子串都能够与一条从起点到该节点的路径，并且这些子串是其中最长串的连续后缀。
例如对于第四个节点，可以对应的子串有 \(\text{aabb,abb,bb}\)，其中 \(\text{aabb}\) 的后缀是 \(\text{abb,bb}\)。

性质三：不同的边

第一种边为图例上的蓝色边。类似字典树，可以接在每一个节点的后面，相当于给这个节点对应的所有子串加上一个字符。
还是用第四个节点举例，它的子串 \(\text{aabb,abb,bb}\) 到达节点六就变成了 \(\text{aabba,abba,bba}\)。

第二种边为图例上的绿色边，称为 link 边或后缀链接。接在每个节点后时，相当于给最短字串去掉一个字符。
第四个节点的最短字串为 \(\text{bb}\)，通过后缀链接到达节点五时变成了 \(\text{b}\)。
这类边能够形成一棵树。

构造思路

SAM 的构造需要一个叫做 \(\operatorname{endpos}\) 的东西。对于一个子串 \(s\)， \(\operatorname{endpos}(s)\) 表示这个子串在字符串中出现时，所有结束位置的集合。

例如对于字符串 \(\text{aabbabd}\)，有 \(\operatorname{endpos}(“ab”)=\{3,6\}\)。

在某些情况下两个子串的 \(\operatorname{endpos}\) 可能相等，例如 \(\operatorname{endpos}(“aabb”)=\operatorname{endpos}(“abb”)=\{4\}\)。这种情况下，这些子串被称为 等价类。SAM 上的所有状态都能和每一个不同的等价类一一对应。

\(\operatorname{endpos}\) 的性质有：

1. 对于两个非空子串 \(s_1\) 和 \(s_2\)（设 \(|s_1|\leq |s_2|\)），若 \(\operatorname{endpos}(s_2)\sube\operatorname{endpos}(s_1)\)，则字符串 \(s_1\) 在 \(s\) 中仅以 \(s_2\) 的后缀形式存在；反之，若两个子串的 \(\operatorname{endpos}\) 完全无交，则 \(s_1\) 不为 \(s_2\) 的后缀。
   由上述性质可以得到一个推论：两个非空子串的 \(\operatorname{endpos}\) 只可能为包含关系或者完全无交。
2. 若 \(\operatorname{endpos}(s_1)=\operatorname{endpos}(s_2)\)，则短字符串为长字符串的后缀。
3. 对于一个 \(\operatorname{endpos}\) 等价类，若对应的最长子串的后缀 \(s\)，满足其长度在最长串与最短串之间，那么 \(s\) 为在等价类对应的集合之中。
   换而言之，对于同一等价类的任一两子串，较短者为较长者的后缀，且该等价类中的子串长度恰好覆盖整个区间。

---

利用 \(\operatorname{endpos}\)，我们就可以建立一个满足前面提到条件的 SAM 了。

构造采用增量插入。初始时 SAM 为空，每次把每个字符串添加进去，然后进行维护。

例题讲解

还是从模板开始。

【模板】后缀自动机

洛谷传送门
给定一个字符串，求出所有出现次数不为 \(1\) 的子串中，出现次数与该子串长度乘积的最大值。

解析：先看看怎么求每个子串的出现次数，相当于求出每个子串的 \(|\operatorname{endpos}|\)。求解时，我们只需要利用后缀链接边。

举一个例子，对于字符串 \(\text{aabcd,babcd}\)，它们不为后缀关系所以 \(\operatorname{endpos}\) 完全无交；但它们都有一个后缀 \(\text{abcd}\)，所以它们又都是 \(\operatorname{endpos}(“abcd”)\) 的一个子集。这也就说明了，所有子节点的 \(\operatorname{endpos}\) 其实是对父节点的一个划分。那么，我们只需要找到对应的父节点集合，并求出所有子节点的 \(|\operatorname{endpos}|\) 之和即可，一个 dfs 就可以搞定。

怎么找集合？其实也很简单，照着定义一步步往下走就行了。

#include <cstring>
#include <iostream>#define Miolic 0using namespace std;const int maxn = 2e6 + 10;  // 节点数为串串长度两倍char s[maxn];
long long ans;class Suffix_Automaton {private:int tot = 1, lst = 1;                      // lst 为上一个状态int head[maxn], nxt[maxn], to[maxn], cnt;  //构造自动机后存图long long f[maxn];  // f[i] 表示第 i 个字串的出现次数struct node {int len, fa;int ch[26];  //当字符集较大时使用 map 或哈希表} node[maxn];void add(int u, int v) { nxt[cnt] = head[u], to[cnt] = v, head[u] = cnt++; }public:void extend(int c) {int p = lst, nxp = lst = ++tot;f[tot] = 1;node[nxp].len = node[p].len + 1;  // 新状态长度等于原状态加一while (p && !node[p].ch[c])       // 一步步向下走node[p].ch[c] = nxp, p = node[p].fa;  // p 向前跳的目的是找到最长串if (!p) return node[nxp].fa = 1, (void)Miolic;//若新串后缀处理结束则直接跳出int q = node[p].ch[c];if (node[q].len == node[p].len + 1)  // 满足条件，直接把父亲向前指node[nxp].fa = q;else {  // 不满足条件，复制一个新节点并维护int nxq = ++tot;node[nxq] = node[q], node[nxq].len = node[p].len + 1;node[q].fa = node[nxp].fa = nxq;while (p && node[p].ch[c] == q) node[p].ch[c] = nxq, p = node[p].fa;}}void build() {  //按照 SAM 建图跑 dfsmemset(head, -1, sizeof(head));for (int i = 2; i <= tot; i++) add(node[i].fa, i);}void dfs(int u) {for (int i = head[u]; ~i; i = nxt[i]) {int v = to[i];dfs(v);f[u] += f[v];}if (f[u] > 1) ans = max(ans, f[u] * node[u].len);}
} SAM;int main(void) {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> (s + 1);for (int i = 1; s[i]; i++) SAM.extend(s[i] - 'a');SAM.build();SAM.dfs(1);cout << ans;return 0;
}

可以发现，SAM 的代码量其实很少（核心代码只有三十来行），写起来也很方便。
上面注释提到，当字符集较大时要考虑使用哈希表或 map，这是因为我们给每个后缀都建了一个 ch 数组，当字符串长度很大时内存开销也非常恐怖 （这题就达到了可怕的 \(2\times10^7\)，已经是内存上限的一半了）。
当然如果用了 map 时间复杂度就要多一个 \(\log n\)，用哈希表同样要大内存，见仁见智吧。

---

下面看几道例题。很多 SAM 的题都可以用其他字符串算法（比如 KMP，AC 自动机，后缀数组）解决，做题时不妨对比一下几种算法的优劣。

[JSOI2012]玄武密码

洛谷传送门
给定一个模式串和若干个匹配串，对每个匹配串找到一个最长前缀的长度，满足该前缀为模式串的子串。

解析：这道题在之前讲 AC 自动机时提到过，可以看看。但是用 SAM 做这题，就非常简单了。

对模式串建立一个 SAM，那么 SAM 上每一个路径都可以对应一个子串。对每一个模式串，直接顺着 SAM 一直走，直到匹配失败时就是最长前缀。

呐，很简单吧？

//板子内容全部略过
inline int get(char c) {if (c == 'E') return 0;if (c == 'S') return 1;if (c == 'W') return 2;return 3;
}class Suffix_Automaton {private://...public://...int solve(char s[]) {int p = 1, res = 0;for (int i = 0; s[i]; i++) {int c = get(s[i]);if (node[p].ch[c])p = node[p].ch[c], res++;elsebreak;}return res;}
} SAM;int main(void) {ios::sync_with_stdio(false);cin.tie(nullptr);cin >> n >> m;cin >> s;for (int i = 0; s[i]; i++) SAM.extend(get(s[i]));while (m--) {cin >> s;cout << SAM.solve(s) << '\n';}return 0;
}