「Note」 后缀自动机

我直接忽略掉这个玩意的原理。

或许我应该从自动机开始，更确切地说我应该从 确定有限状态自动机 ($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;

$\mathtt{DFA \ minimization}$