「笔记」后缀自动机

2024-04-09 19:57:47

写在前面

遇到某些看做很扯的定义时暂时不要考虑正确性，应用之类，只需记住就好，这些东西在下文中一般都有详细介绍。

前置知识

个人理解（没那么严谨的定义）：
一个确定有限状态自动机 (DFA) 是一个边上带有字符的有向图。
节点被称为状态，边被称为 转移函数。存在一个指定的 起始状态，和多个 接受状态。

DFA 可接受一个字符串，并对其进行判定。一个 DFA 读入一个字符串后，会从起始状态开始，按照转移函数一个一个字符进行转移，转移函数的字符与字符串对应位置字符相同。
读入完成后，若字符串位于一个接受状态，则称 DFA 接受这个字符串，反之称 DFA 不接受 这个字符串。若转移过程中不存在对应某字符的转移函数，也称 DFA不接受这个字符串。

Trie, KMP, AC自动机，SAM，广义SAM 都是自动机。

引入

给定字符串 \(S\)，构建一个可识别其子串的 DFA。

能识别所有子串，则该 DFA 需要包含所有子串的信息。最直观的思路是用 \(S\) 所有子串建立一棵 Trie，将每个子串的结尾作为接受状态。

但这棵 Trie 有两个问题，一是大量子串是其他子串的前缀，Trie 的节点数量实际上只有 \(O(n^2)\) 级别。二是除起始状态外的所有状态都是接受状态，一个字符串不是 \(S\) 的子串，等价于转移时不存在对应串中某字符的 转移函数。
可以发现，构建这棵 Trie 时，仅将所有后缀插入进去，将后缀的结尾作为 接受状态 即可。使用时仅需判断最终状态是否在 Trie 上。

这东西长得怎么这么熟悉？发现这是一棵支持接受后缀的后缀树。
后缀自动机就是一种具有这样的性质和功能的能够支持更多功能的数据结构。

SAM 的定义

字符串 \(S\) 的后缀自动机 (suffix automaton, SAM) 是一个接受 \(S\) 所有后缀的 最小的 DFA。
更形式化的定义：

字符串 \(S\) 的 SAM 是一张 DAWG（有向单词无环图）。节点被称作状态，边被称作状态间的转移。
存在一个起始节点，称作 起始状态。其它节点均可从起始节点出发到达。
每个转移都标有一些字母。从一个节点出发的所有转移均不同。
存在数个 终止状态。若从 \(t_0\) 出发，最终转移到一个终止状态，路径上所有转移连接起来一定是 \(S\) 的一个后缀。\(S\) 的每个后缀均可用一条从起始节点到某个终止状态的路径构成。
在所有满足上述条件的 DFA 中，SAM 的节点数是最少的。

SAM 并不是一个典型的 DFA，在 DAWG 基础上，除 \(t_0\) 外的每个状态都被添加了一条 后缀链接。所有后缀链接组成了树状结构，这棵树被称为 parent 树。

字符串 \(S\) 的 SAM 能包含 \(S\) 所有子串的信息。
SAM 将这些信息以高度压缩的形式储存，对于一个长度为 \(n\) 的字符串，它的 SAM 空间复杂度仅为 \(O(n)\)，构建 SAM 的时间复杂度也仅为 \(O(n)\)。

独特概念

结束位置 endpos

对于 \(S\) 的任意非空子串 \(T\)，记 \(\operatorname{endpos}(T)\) 为子串 \(T\) 在 \(S\) 中的 所有结束位置 组成的集合。
如 \(S=114514, \operatorname{endpos}(14)=\{3,6\}\)。
对于两个子串 \(t_1,t_2\)，若 \(\operatorname{endpos}(t_1)=\operatorname{endpos}(t_2)\)，则称 \(t_1,t_2\) 属于一个 \(\operatorname{endpos}\) 等价类。

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

引理 1：对于非空子串 \(t_1,t_2\ (\left| t_1\right| \le \left| t_2\right|)\)，\(\operatorname{endpos}(t_1)=\operatorname{endpos}(t_2)\iff t_1\) 在 \(S\) 中每次出现，都是以 \(t_2\) 的后缀形式存在。

引理 2：对于非空子串 \(t_1,t_2\ (\left| t_1\right| \le\left| t_2\right|)\)，\(\operatorname{endpos}(t_1)\) 和 \(\operatorname{endpos}(t_2)\) 的关系取决于 \(t_1\) 是否为 \(t_2\) 的后缀：

\[\begin{cases} \operatorname{endpos}(t_2) \subseteq \operatorname{endpos}(t_1) &\operatorname{t_1\ is\ a\ suffix\ of\ t_2}\\ \operatorname{endpos}(t_2) \cap \operatorname{endpos}(t_1)=\varnothing &\operatorname{otherwise}\\ \end{cases}\]

引理 3：对于一个 \(\operatorname{endpos}\) 等价类，将类中所有字符串按照长度非递增顺序排序。
则每个字符串都是前一个的后缀，且长度为上一个的长度 \(-1\)。
即：\(\operatorname{endpos}\) 等价类中的串为 \(S\) 的 某前缀的长度连续的后缀。

三个引理正确性显然，读者感性理解即可。

DAWG

考虑引入部分中的节点数为 \(O(n^2)\) 级别的后缀树，它满足下列性质：

每个状态唯一对应一个子串，\(t_0\) 对应空串 \(\varnothing\)。
从 \(t_0\) 出发，沿转移边移动，每条路径都唯一对应 \(S\) 的一个子串。
每个子串也唯一对应某条从 \(t_0\) 出发的路径，所有子串都可以被某条路径表示出来。

SAM 满足上述性质 2，3，对于上述性质 1，SAM 对信息进行了压缩，每个状态可表示一个或多个子串，从而得到了 DAWG。
到达某状态的路径可能不止一条。一个状态对应一些子串的集合，集合的元素分别对应这些路径。不存在可代表同一子串的两个不同状态，因为每个子串唯一对应一条路径。

规定：除 \(t_0\) 外，每个状态都是不同的 \(\operatorname{endpos}\) 等价类，对应该等价类内子串的集合。
即 SAM 由起始状态 \(t_0\) 和每一个 \(\operatorname{endpos}\) 等价类对应的状态组成。

此规定是 SAM 的精髓。
SAM 的状态数等价于 \(\operatorname{endpos}\) 等价类的个数 \(+1\)，而 \(\operatorname{endpos}\) 等价类的个数仅为 \(O(n)\) 级别，在复杂度这一小节会给出证明。

再引入一些概念：

对于一个状态 \(v\)，记 \(\operatorname{longest}(v)\) 为其可代表的最长的字符串，记 \(\operatorname{len}(v)\) 为 \(\operatorname{longest}(v)\) 的长度。
类似地，记 \(\operatorname{shortest}(v)\) 为最短的子串，记其长度为 \(\operatorname{minlen}(v)\)。

由 endpos 引理 3，每个状态代表着 某个前缀长度连续的后缀。
则状态 \(v\) 中所有字符串都是 \(\operatorname{longest}(v)\) 的不同的后缀，且所有字符串的长度覆盖区间 \([\operatorname{minlen}(v), \operatorname{len}(v)]\)。

对于字符串 \(S=\text{514141}\)，它的 DAWG 有下图所示，至于为什么是这个形态，请继续往下看。

后缀链接 Link

对于两个状态 \(u,v\ (u\not ={t_0})\)，定义 \(u\) 的后缀链接 \(\operatorname{Link}(u)\) 指向 \(v\)，当且仅当 \(\operatorname{minlen}(u) = \operatorname{len}(v) + 1\)，且 \(v\) 代表的子串均为 \(u\) 的后缀。
记作 \(\operatorname{Link}(u)=v\)。

从定义中可以得到后缀链接的一些性质：

若 \(\operatorname{minlen}(u) = 1\)，则 \(\operatorname{Link}(u) = t_0\)。
\(\operatorname{minlen}(u) = \operatorname{len}(v) + 1\)，再结合引理 3 的单调性可知，\(\operatorname{Link}(u)\) 所对应的字符串严格短于 \(u\) 所表示的字符串。
\(v\) 代表的子串均为 \(u\) 的后缀，再结合引理 2 可知 \(\operatorname{endpos}(u) \subseteq \operatorname{endpos}(\operatorname{Link}(u))\)。
结合性质 2，3，\(\operatorname{Link}(u)\) 是所有满足 \(\operatorname{endpos}(u) \subseteq \operatorname{endpos}(v)\) 的状态 \(v\) 中 \(\left| \operatorname{endpos}(v)\right|\) 最小的。即 \(\operatorname{longest}(\operatorname{Link}(u))\) 为 \(\operatorname{shortest}(u)\) 的次长后缀（最长为 \(\operatorname{shortest}(u)\) 本身）。

引理 4：所有后缀链接构成一棵根节点为 \(t_0\) 的树。

正确性显然，由性质 2 可知，\(\operatorname{Link}(u)\) 所对应的字符串严格短于 \(u\) 所表示的字符串，沿着后缀链接移动，最终总能到达空串，即起始状态。则通过 \(\operatorname{Link}\) 构成的图中不会出现环。
这棵树被称为字符串 \(S\) 的 parent 树。

parent 树

所有后缀链接构成的一棵根节点为 起始状态 的树，它有如下性质：

结合后缀链接的性质 3，在这棵树上总有 \(\operatorname{endpos}(son)\subsetneq \operatorname{endpos}(father)\)。且对于同一个 \(father\) 的不同 \(son\)，有 \(\operatorname{endpos}(son_i)\cap \operatorname{endpos}(son_j)=\varnothing\ (i\not ={j})\)。
从一个状态 \(v\) 沿后缀链接遍历 parent 树，总会到达 \(t_0\)。
经过的状态代表的字符串的区间互不相交，且它们所代表的子串的并集是一个连续的区间 \([0, \operatorname{len}(v)]\)，代表 \(S\) 长度为 \(\operatorname{len}(v)\) 的前缀的所有后缀。

由性质 2，可知 parent 树本质上是由 \(\operatorname{endpos}\) 集合构成的树，体现了 \(\operatorname{endpos}\) 的包含关系。
对于字符串 \(S=\text{514141}\)，它的 parent 树有图中粉色边所示：

定理：字符串 \(S\) 的 parent 树为 \(S\) 的反串的后缀树。

证明可以考虑 \(\operatorname{endpos}(u)\) 与 \(\operatorname{endpos}(\operatorname{Link}(u))\) 的关系。\(\operatorname{longest}(\operatorname{Link}(u))\) 为 \(\operatorname{shortest}(u)\) 的次长后缀。
则 \(\operatorname{shortest}(u)\) 可在 \(\operatorname{longest}(\operatorname{Link}(u))\) 基础上，在头部添加一个字符得到。
在正串的头部添加字符构成正串的后缀，等价于在反串尾部添加字符构成反串的后缀，构建正串的 SAM 的过程，等价于构建反串后缀树的过程。

小结

~~上面说的玩意全都忘光了，好耶！~~

\(S\) 的子串可根据结束位置 \(\operatorname{endpos}\) 划分为多个 \(\operatorname{endpos}\) 等价类。
SAM 由起始状态 \(t_0\) 和每一个 \(\operatorname{endpos}\) 等价类对应的状态组成。
对于一个状态 \(v\)，记 \(\operatorname{longest}(v)\) 为其可代表的最长的字符串，记 \(\operatorname{len}(v)\) 为其长度。类似地，记 \(\operatorname{shortest}(v)\) 为最短的子串，记其长度为 \(\operatorname{minlen}(v)\)。
对于两个状态 \(u,v\ (u\not ={t_0})\)，\(\operatorname{Link}(u)=v\)，当且仅当 \(\operatorname{minlen}(u) = \operatorname{len}(v) + 1\)，且 \(v\) 代表的子串均为 \(u\) 的后缀。
所有后缀链接构成一棵根节点为 \(t_0\) 的树，被称为字符串 \(S\) 的 parent 树。

构建 SAM

特别鸣谢：后缀自动机多图详解（代码实现） - maomao9173

使用增量法完成 SAM 的构建。具体地，已知 \(S\) 的 SAM，考虑如何对其进行修改，得到 \(S+c\) （\(c\) 是一个字符）的 SAM。

加入字符 \(c\) 后，子串只新增加了 \(S + c\) 的后缀，已有的子串不受影响。
但 \(S + c\) 的某些后缀可能在 \(S\) 出现过，在 SAM 中有其对应的状态。SAM 中一个串只能对应一个状态，需考虑将它们对应到相应状态上。

初始化与判断

设 \(last\) 是代表字符串 \(S\) 的状态。显然串 \(S + c\) 在 \(S\) 中不可能出现，它一定被对应到新状态上。
设新状态为 \(now\)，则必有 \(\operatorname{len}(now) = |S+c| = \operatorname{len}(last) + 1\)。

考虑如何判断 \(S + c\) 的后缀在 \(S\) 出现过。\(S + c\) 的后缀等于 \(S\) 的后缀 \(+ c\)，则仅需判断 \(S\) 的后缀有无转移边 \(c\) 即可。
若 \(S\) 的某后缀有转移边 \(c\)，它一定是新串的后缀，且说明 \(S+c\) 的该后缀在 \(S\) 中出现过。若没有转移边 \(c\)，则它应向 \(now\) 连一条转移边 \(c\)。

由 parent 树的性质 2，从代表 \(S\) 的状态沿 \(\operatorname{Link}\) 遍历至 \(t_0\)，等价于按长度递减遍历原串的所有后缀，则有如下代码：

for (; p && ! ch[p][c_]; p = link[p]) ch[p][c_] = now;

枚举到第一个这样的状态 \(p\) 即可。
因为 parent 树上 \(p\) 的祖先代表的串，均为 \(p\) 代表的串的后缀。它们短于 \(p\) 代表的串，并且一定也有转移边 \(c\)，也一定为 \(S+c\) 的后缀。
换言之，状态 \(p\) 是 代表的串最长 的、满足有转移边 \(c\) 的、代表了 \(S\) 的后缀的状态。

讨论

为得到 \(\operatorname{Link}(now)\)，下面将对\(S + c\) 的后缀在 \(S\) 中是否出现进行讨论。

case 1：若 \(S + c\) 的所有后缀在 \(S\) 中均未出现。可直接将新状态的 \(\operatorname{Link}\) 指向起始状态。此时新状态代表 \(S + c\) 的所有后缀 \([1, |S + c|]\)。

if (! p) {link[now] = 1; return ;}

case 2：若 \(S+c\) 的某后缀在 \(S\) 中出现过，
且对于包含此子串的状态 \(q\)，有 \(\operatorname{len}(q)=\operatorname{len}(p) +1\)。

则 \(q\) 代表的 所有串，及 parent 树上它的所有祖先代表的串，均为 \(S + c\) 的后缀。

\(\operatorname{longest}(q)\) 为 \(S+c\) 的后缀，应有 \(\operatorname{Link}(now) = q\)。
此时 \(now\) 代表 \(S + c\) 的后缀 \([\operatorname{len}(q) + 1, |S + c|]\)。

int q = ch[p][c_];
if (len[q] == len[p] + 1) {link[now] = q; return ;}

case 3：\(S+c\) 的某后缀在 \(S\) 中出现过，
但对于包含此子串的状态 \(q\)，有 \(\operatorname{len}(q)\not= \operatorname{len}(p) +1\)。
首先有 \(\operatorname{len}(q)> \operatorname{len}(p) +1\)。，因为 \(p\) 经转移边 \(c\) 后可转移到 \(q\)，\(\operatorname{len}(q)<\operatorname{len}(p)+1\) 不成立。

但 \(q\) 中长度 小于等于 \(\operatorname{len}(p) + 1\) 的串，及 parent 树上它的祖先代表的串，为 \(S + c\) 的后缀。
考虑将 \(q\) 拆成 \(S + c\) 的后缀部分，和非 \(S + c\) 的部分。
设将 \(q\) 的 \(S + c\) 的后缀部分放入状态 \(newq\) 中，其余的保留在 \(q\) 中。

\(newq\) 应继承 \(q\) 的转移，因为 \(newq\) 中的串与 新的 \(q\) 的串为后缀关系。
转移同样字符后也为后缀关系，应位于同一状态中

int newq = ++ node_num;
len[newq] = len[p] + 1;
memcpy(ch[newq], ch[q], sizeof(ch[q]));

\(newq\) 的串长度小于 \(q\) 的串，且均为 \(q\) 的后缀，则 \(\operatorname{Link}(newq) = \operatorname{Link}(q)\)。

link[newq] = link[q];

有 \(\operatorname{len}(newq) + 1 = \operatorname{minlen}(q)\)，则 \(\operatorname{Link}(q) = newq\)。

link[q] = newq;

\(newq\) 代表的所有串，及 parent 树上它的祖先代表的串，均为 \(S + c\) 的后缀。
应有 \(\operatorname{Link}(now) = newq\)。这样 \(now\) 代表 \(S + c\) 的后缀 \([\operatorname{len}(newq) + 1, |S + c|]\)。

link[now] = newq;

最后枚举所有可以转移到 原来的 \(q\) 的比 \(p\) 短的 \(S\) 的后缀，将其指向 \(newq\)。
这样是对的，因为 \(\operatorname{len}(newq) = \operatorname{len}(p) + 1\)，\(p\) 应转移到 \(newq\)，则比 \(p\) 的串还短的后缀也应转移到 \(newq\)。
应转移到 新的 \(q\) 的后缀的转移不会被修改。

for (; p && ch[p][c_] == q; p = link[p]) ch[p][c_] = newq;

代码

P3804 【模板】后缀自动机 (SAM)

建出 SAM 后在 parent 树上 DP 即可。

//知识点：SAM
/*
By:Luckyblock
试了试变量写法，挺清爽的。
*/
#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#define ll long long
const int kMaxn = 1e6 + 10;
const int kMaxm = 26;
//=============================================================
int n, last = 1, node_num = 1; //注意 1 为起始状态，其他状态的标号从 1 开始。 
int ch[kMaxn << 1][kMaxm], len[kMaxn <<1], link[kMaxn << 1]; //SAM
int edge_num, v[kMaxn << 1], ne[kMaxn << 1], head[kMaxn << 1]; //Graph
ll ans, size[kMaxn << 1];
char S[kMaxn];
//=============================================================
inline int read() {
  int f = 1, w = 0;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -1;
  for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
  return f * w;
}
void GetMax(ll &fir, ll sec) {
  if (sec > fir) fir = sec;
}
void AddEdge(int u_, int v_) {
  v[++ edge_num] = v_, ne[edge_num] = head[u_], head[u_] = edge_num;
}
void Insert(int c_) { //原串 S -> 新串 S + c
  int p = last, now = last = ++ node_num; //创建新状态 now
  size[now] = 1, len[now] = len[p] + 1; //仅为终止状态 size 赋值。

  //按长度递减 枚举代表 S 后缀的状态 p。
  //检查 S 中是否存在子串，为新串的后缀。  
  //等价于检查 S 后缀有无 c 的转移（S + c 的后缀 = S 的后缀 + c）。
  for (; p && ! ch[p][c_]; p = link[p]) ch[p][c_] = now;
  
  //原串中不存在子串，为新串的后缀。  
  //直接将新状态的 link 指向 起始状态。  
  //此时新状态代表 S + c 的所有后缀 [1, |S + c|]。  
  if (! p) {link[now] = 1; return ;} 

  //原串中存在子串 为新串的后缀。  
  //且包含此子串的状态 q 中最长串的长度 为 p 最长串长度 + 1。  
  //则 q 代表的所有串，及 parent 树上它的祖先代表的串，均为 S + c 的后缀。
  //应有 Link(now) = q。这样 now 代表 S + c 的后缀 [len(q) + 1, |S + c|]。
  int q = ch[p][c_];
  if (len[q] == len[p] + 1) {link[now] = q; return ;}

  //原串中存在子串 为新串的后缀。  
  //但包含此子串的状态 q 中最长串的长度 不为 p 最长串长度 + 1。  
  //首先，q 中最长串的长度 必大于 p 最长串长度 + 1，因为 p + c 后可转移到 q。  
  //因为 S 的后缀 + c 可转移到 q，则 q 中长度 **小于等于**  len[p] + 1 的串，及 parent 树上它的祖先代表的串，为 S + c 的后缀。
  //考虑将 q 拆成 S + c 的后缀部分，和非 S + c 的部分。
  //下面代码把 S + c 的后缀部分放到了 newq 中，其余的保留在 q 中。

  //newq 应继承 q 的转移，因为 newq 与 新的 q为后缀关系。
  //转移同样字符后也为后缀关系。  
  int newq = ++ node_num;
  memcpy(ch[newq], ch[q], sizeof(ch[q])); 

  //newq 的串长度小于 q 的串，且均为 q 的后缀，则 Link(newq) = Link(q)。
  link[newq] = link[q], len[newq] = len[p] + 1; 

  //有 len(newq) + 1 = minlen(q)，则 Link(q) = newq。
  //则 newq 代表的所有串，及 parent 树上它的祖先代表的串，均为 S + c 的后缀。
  //应有 Link(now) = newq。这样 now 代表 S + c 的后缀 [len(newq) + 1, |S + c|]。
  link[q] = link[now] = newq; 

  //最后枚举所有 可以转移到 **原来的 q** 的 S 的，比 p 短的后缀，将其指向 newq。
  //这样是对的，因为 len(newq) = len(p) + 1，比 p 的串还短的后缀 应该转移到 newq。
  //能够转移到 **新的 q** 的后缀 的转移不会被修改。
  for (; p && ch[p][c_] == q; p = link[p]) ch[p][c_] = newq;
}

//parent 树上 DP，用孩子更新父亲。
//孩子的长度比父亲长，则孩子出现的地方，父亲一定出现，size 累加。
//父亲的 size 也可能不为 0（为终止状态）。
void Dfs(int u) { 
  for (int i = head[u]; i; i = ne[i]) {
    Dfs(v[i]);
    size[u] += size[v[i]];
  }
  if (size[u] > 1) GetMax(ans, 1ll * size[u] * len[u]);
}
//=============================================================
int main() {
  scanf("%s", S + 1);
  int n = strlen(S + 1);
  for (int i = 1; i <= n; ++ i) Insert(S[i] - 'a');
  for (int i = 2; i <= node_num; ++ i) AddEdge(link[i], i);
  Dfs(1);
  printf("%lld\n", ans);
  return 0; 
}

复杂度

一些分析。

状态数

对于一个长度为 \(n\ (n\ge 2)\) 的字符串 \(S\)，它的 SAM 的状态数 \(\le 2n-1\)。

考虑 parent 树中父子节点的关系。
由 parent 树的性质 1，在 parent 树上总有 \(\operatorname{endpos}(son)\subseteq \operatorname{endpos}(father)\)。
对于同一个 \(father\) 的不同 \(son\)，有 \(\operatorname{endpos}(son_i)\cap \operatorname{endpos}(son_j)=\varnothing\ (i\not ={j})\)。

对于一个父节点，其若干个儿子的 \(\operatorname{endpos}\) 相当于将父节点的 \(\operatorname{endpos}\) 分割成的若干不相交子集，最终会产生不多于 \(n\) 个叶节点。
一个分叉点会合并至少两个点，parent 树为完全二叉树时节点数最多，为 \(2n-1\) 个。
此时 parent 树表示的的集合关系类似一棵线段树。
大概有下图的感觉：

也可用算法本身证明。
最开始自动机仅含有起始状态，前两次迭代中仅会创建一个节点，剩余 \(n-2\) 步中每步至多会创建 \(2\) 个状态。

状态数在 \(S\) 形如 \(\operatorname{abb\cdots }\) 时取到上界。

转移数

对于一个长度为 \(n\ (n\ge 3)\) 的字符串 \(S\)，它的 SAM 的转移数 \(\le 3n-4\)。

假设已按照上述算法建出字符串 \(S\) 的 SAM。

考虑对 DAWG 建一棵生成树，钦定 \(t_0\) 为根。
已知状态数 \(\le 2n-1\)，则树上的转移数 \(\le 2n-2\) 条。
接下来仅需考虑在 DAWG 上，不在生成树上的转移。

考虑一个非树上转移 \((u,v)\)，可以找到下面三段字符串：

沿树上转移从根 \(t_0\) 到 \(u\) 得到的字符串 \(t_0\rightarrow u\)。
转移 \((u,v)\) 上的字符。
沿 字符字典序最小 的转移（在不在树上均可），直到到达一个接受状态 \(w\) 得到的字符串 \(v\rightarrow w\)。

状态 \(u,v\) 确定，则 \((u,v)\) 是唯一的。
记 \(T = t_0\rightarrow u +(u,v) + v\rightarrow w\)，上述三段字符串都是唯一的，则 \(T\) 是唯一的。
又 \(T\) 从 \(t_0\) 出发，最终到达了接受状态，则 \(T\) 为 \(S\) 的一个后缀。
并且 \((u,v)\) 是按上述方式运行时，\(T\) 经过的第一条 非树上转移。

则一条非树上转移 唯一对应 一个字符串的后缀。
被对应 的后缀 唯一对应 一条非树上转移。
后缀个数为 \(n\)，显然长度为 \(1\) 的后缀不对应非树上转移，则非树上转移数 \(\le n - 1\)。

两者相加，得到转移数的上界为 \(3n-3\)。
但状态数为 \(2n-1\) 时，\(S\) 形如 \(\operatorname{abb\cdots bb}\)，此时转移数 \(< 3n-3\)。
转移数实际的上界为 \(3n-4\)，在 \(S\) 形如 \(\operatorname{abb\cdots bbc}\) 时取到。

SAM 的空间复杂度

写成这样 int ch[kMaxn << 1][kMaxm];，空间 \(O(n|\sum|)\)，查询时间 \(O(1)\)。
字符集较大时，可写成这样 map<int,int> ch[kMaxn << 1]，空间 \(O(n)\)，查询时间 \(O(\log |\sum|)\)。

构建 SAM 的时间复杂度

均摊 \(O(n)\)，写这个挺浪费时间的也没什么用，跑路了。

写在最后

参考资料：

OI-wiki SAM
后缀自动机学习笔记 _ Menci's Blog
博文 Суффиксный автомат 版权协议为 Public Domain + Leave a Link
博文 Суффиксный автомат 的英文翻译版 Suffix Automaton 版权协议为 CC-BY-SA 4.0
史上最通俗的后缀自动机详解 - KesdiaelKen 的博客
 后缀自动机多图详解（代码实现） - maomao9173
《后缀自动机》 - 陈立杰

码农公寓