我直接忽略掉这个玩意的原理。
或许我应该从自动机开始，更确切地说我应该从 确定有限状态自动机 (\(DFA\)) 开始。
\(\mathbb{DFA}\)
\(\mathtt{Definition}\)
首先给出一些前置的定义。
- \(Q\)，有限状态集合。
- \(\Sigma\)，有限字符集。
- \(\delta\)，转移函数， \(Q \times E \rightarrow Q\)。
- \(q_0\)，起始状态。
- \(F \subset Q\)，接受状态集合。
设 \(N = (Q, \Sigma, \delta, q_0, F)\) ，定义 \(E(q)\) 表示从 状态 \(q\) 出发，只沿着 \(\epsilon\) 转移能够到达的集合。
然后构造 \(M = (Q', \Sigma, \delta', E(q_0), F')\)，其中
- \(Q'\)，状态集合， \(Q' = \mathcal{P}(Q)\)
- \(\delta'\)，转移函数，\(Q' \times E \rightarrow Q',\delta'(S, c) = \bigcup q \in S, q' \in \delta(q, c) E(q')\)
- \(F'\)，终止状态集合，\(F' = \{ S \subset Q \mid S \cap F \not = \empty \}\)。
工作时自动机会一个一个读入字符集，按照 \(\delta\) 转移，如果在转移结束之后处于一个接受状态，那么成这个自动机接受这个字符串，反之称这个自动机不接受这个状态。
当一个状态 \(S\) 没有字符 \(c\) 的转移时，令 \(\delta(S, c) = \mathrm{null}\) ，\(\mathrm{null}\) 不属于任何接受状态，也无法进行转移。
于是我们可以简单地定义自动机了。
\(\mathbb{SAM}\)
\(\mathtt{Definition}\)
一个字符串的 后缀自动机（\(\mathrm{SAM}\)） 就是一个 接受且仅接受 这个字符串的 所有后缀 的 \(DFA\) 。
那么根据定义，如果一个字符串 \(t\) 是 \(s\) 的后缀，当且仅当 \(\mathrm{SAM}_{s}(t) = \mathtt{true}\) ，同样可以知道，如果一个字符串 \(t\) 是 \(s\) 的子串，当且仅当 \(\delta_s(t) \not= \mathrm{null}\) ，很好理解，因为如果在 \(t\) 的后面增加一些字符成为 \(t'\)，\(t'\) 一定是 \(s\) 的后缀。
\(\mathtt{Construction}\)
考虑一下，还是先写构造的方式。
\(\Theta(n^2) \ \mathrm{SAM}\)
首先看一个很简单的 \(\mathrm{SAM}\) ，即是说建一棵字典树，直接把所有后缀塞进去，每次标记终止节点为接受状态，就可以得到一个状态数 \(\Theta(n^2)\) 的 \(\mathrm{SAM}\) 。
\(\Theta(n) \ \mathrm{SAM}\)
然后应用关于自动机的一些科技，对这个玩意进行 任意 \(DFA\) 压缩 。
首先写对 \(\Theta(n^2) \ \mathrm{SAM}\) 的压缩，最后写个泛化的压缩方式。
下面定义一些变量。
\(\mathtt{right \ \& \ reg}\)
注意到这个是个集合，对于一个字符串 \(t\) ，如果它在 \(s\) 中出现的位置的集合为 \(\{ [l_1, r_1), [l_2, r_2), \dots [l_n, r_n)\}\) ，那么 \(\mathtt{right}(t) = \{ r_1, r_2, \dots, r_n \}\) 。
定义 \(\mathtt{right}\) 集合的等价类为所有 \(\mathtt{right}\) 集合相等的字符串， \(\mathtt{reg}(v)\) 表示从状态 \(v\) 开始能识别的字符串的集合，就是说 \(t \in \mathtt{reg}(v) \Leftrightarrow \delta (v, t) \in F\) 。
这时我们给 字符串 \(t\) 后面接上一个字符串 \(s[r_i, n], r_i \in \mathtt{right}(t)\) 变成 \(t'\) 使得 \(t'\) 成为 \(s\) 的后缀，所以如果 \(\mathtt{right}(t_1) = \mathtt{right}(t_2)\) ，那么 \(\mathtt{reg}\mathrm{(SAM)}(t_1) = \mathtt{reg}\mathrm{(SAM)}(t_2) = s[r_i, n], r_i \in \mathtt{right(t_1)}\)。
这样的 \(\mathrm{SAM}\) 的状态数是最少的当且仅当 \(\mathtt{reg}\) 集合对应的状态两两不同。
\(\mathtt{minl \ \& \ maxl}\)
表示 这个状态下对应的最长的字符串和最短的字符串 。
根据定义可以知道 \(v\) 对应的任意一个字符串都是 \(\mathtt{maxl}(v)\) 的后缀，且不是 \(\mathtt{minl}(v)\) 的真后缀。并且，\(v\) 包含了所有这样的字符串。
\(\mathtt{parent}\)
后面简写为 \(\mathtt{par}\) 。
对于每个状态 \(v\) ，\(\mathtt{minl}(v)[1, n - 1]\) 对应的状态。
根据定义可知 \(\mathtt{len}(\mathtt{minl}(v)) = \mathtt{len}(\mathtt{maxl}(v)) + 1\) ，并且可以发现由指向 \(\mathtt{par}\) 的边可以构成一棵树，称为 \(\mathtt{par}\) 树。
此时 \(\mathrm{SAM}\) 上的接受状态就是包含 \(r_i = n\) 的一些 \(\mathtt{right}\) 集合的等价类，那么反过来我们可以通过 \(\mathtt{par}\) 树确定 \(\mathrm{SAM}\) 上面可接收状态的集合。
\(\mathtt{Code}\)
struct SuffixAutomaton {
int siz, last;
LL tot;
struct Node { int len, par; map<char, int> nxt; } s[MAXN << 1];
void init() { s[0].len = 0, s[0].par = -1, siz = 1, last = 0; }
void extend(char c) {
int cur = ++siz;
s[cur].len = s[last].len + 1;
int p = last;
while (p != -1 && !s[p].nxt.count(c)) {
s[p].nxt[c] = cur;
p = s[p].par;
}
if (p == -1) {
s[cur].par = 1;
} else {
int q = s[p].nxt[c];
if (s[p].len + 1 == s[q].len) {
s[cur].par = q;
} else {
int clone = ++siz;
s[clone].len = s[p].len + 1;
s[clone].nxt = s[q].nxt;
s[clone].par = s[q].par;
while (p != -1 && s[p].nxt[c] == q) {
s[p].nxt[c] = clone;
p = s[p].par;
}
s[q].par = s[cur].par = clone;
}
}
last = cur;
tot += s[cur].len - s[s[cur].link].len;
}
} sam;