SAM 的线性时间复杂度证明
Wxb2010
·
2026-04-22 17:51:59
·
算法·理论
声明
采用 CC BY-NC-SA 4.0 协议授权，转载须注明出处，演绎作品须使用相同协议共享。
前言
本文参考学术论文，侧重于后缀自动机（SAM，国外称为 DAWG）的构建的时间复杂度证明。
也有讨论了关于广义 SAM 的时间复杂度。
:::info[注]
由于上面的链接是国外的，不保证任意时刻都能访问，所以想要保证长期能够学习的话，建议保存为 PDF。
此外，原论文发表于 1985 年，PDF 形式有 1.57MB，所以本文仅呈现其中一小部分，加入一些了笔者的理解，也有一定程度的本土化处理。
:::
本文参考了 OI-Wiki 中的一些内容。
::::info[写作原因]
在 2015 年国家集训队论文《后缀自动机及其应用》（by 张天扬）中，有如下一段话：
如果没有特殊说明，我们认为字符集为所有小写字母。并且把字符集大小视为常数，在计算复杂度的时候不予考虑。
然而，其复杂度证明中并没有证明重定向的复杂度，仅证明状态数和转移数。不理解忽略字符集的行为。
:::info[注]{open}
假设不忽略字符集时间复杂度为 O(n|\Sigma|) ，那字符集很大时使用 map 时间复杂度会不会是 O(n|\Sigma|\log{|\Sigma|}) 的呢？
并没有说明字符集影响了什么。
:::
某知乎文章，重定向复杂度证明缺失。
不理解某些题解指着一份 memcpy 转移边或结构体复制的代码说：复杂度为 O(n) 。应为 O(n|\Sigma|) ，其中 |\Sigma| 为字符集大小。
总之，相当一部分选手是不了解 SAM 的时间复杂度证明的。
::::
由于 SAM 的结构不太直观，还同时有后缀自动机（DAG）、后缀链接树、字符串本身三个角度，有些性质不容易被注意，所以文章比较啰嗦地强调了一些内容。觉得冗长的大佬可以只看名词与记号 和引理 部分。
建议学习过 SAM 后再阅读，本文对于一些性质只强调不证明。因为我证这些性质会有循环论证的感觉。
感谢 LA 群群友，UOJ 用户群群友，同学 TP2010 和大佬 huangyingjie 的一起讨论。
如果想进一步了解自动机有关理论，加深对 SAM 的理解，推荐阅读有限状态自动机笔记 by 同学 MZMTab。
前置内容
结点 和状态 两个概念有混用的情况，认为它们是等价的即可。
名词与记号
主边（primary edge）：对于转移边 (u,v) ，若满足 \operatorname{len}(u)+1=\operatorname{len}(v) 则称其为主边 。
次级边（secondary edge）：对于转移边 (u,v) ，若满足 \operatorname{len}(u)+1<\operatorname{len}(v) 则称其为次级边 。
:::info[注]{open}
后缀链接树，国内选手有称 Parent 树。
主边和次级边在 OI-Wiki 上是叫连续的转移边和不连续的转移边。
:::
:::info[注]{open}
国内也有 \operatorname{Right} 等称呼，\operatorname{endpos} 对子串定义，\operatorname{end-set} 对状态定义，本质上相同，故有些结论可以直接应用。
:::
构建流程
初始时，仅有结点 t_0=0 ，取 last\leftarrow 0 。
增量构造，插入字符 a 时，新建结点 np ，设置 \operatorname{len}(np)=\operatorname{len}(last)+1 ，进行如下过程：
记 p=last 。
若没有 a 转移边，则新建一条 a 转移边 (p,np) ；若有，退出此过程。
此时有三种情况：
若 p=-1 ，则取 fa(np)\leftarrow 0 ，将 last 修改为 np ，结束本次插入。
记 q 为 p 的 a 转移边的终点，若 (p,q) 为主边，则取 fa(np)\leftarrow q ，结束本次插入。
其它情况，则进行如下过程：
新建结点 nq ，复制 q 结点所有转移边，同时 fa(nq)\leftarrow fa(q),\operatorname{len}(nq)\leftarrow \operatorname{len}(p)+1 。
设置 fa(q)\leftarrow nq,fa(np)\leftarrow nq ，将 last 修改为 np ，完成本次插入。
复杂度证明
状态数和转移数
结论一：SAM 中点的数量 \le 2n+1 。
从构建过程容易看出，事实上，可以分析到 \le 2n-1 ，但不重要。
结论二：SAM 中转移边的数量 \le 3n 。
首先构建一棵仅有主边构成的外向生成树，且此生成树恰好包括所有主边。
:::info[证明]
这样的生成树一定存在，考虑对于每一个结点 v(v\ne t_0) ，\operatorname{longest}(v) 抹去最后一个字符后的字符串，经 SAM 转移一定不会到达 v ；若不然 \operatorname{longest}(v) 一定全相同（仅包含一种字母），而此种情况模拟知不满足，矛盾。
那么就一定有一个结点 u ，满足 \operatorname{len}(u)+1=\operatorname{len}(v) 且存在 (u,v) 转移边。
对于每一个 v ，这样的 u 是唯一的。若不然，存在两个状态能由同一个字符串经 SAM 转移得到，这是不可能的。
:::
则主边总数不超过 2n ，现在只需要次级边。采取构造映射的方法。
此处，我们规定：终止状态为能够接受 s 的后缀的状态。
则对于一条次级边 (p,q),p\xrightarrow{c}q ，则构造一个字符串 \alpha=u+c+v ，其中 u 表示从 t_0 开始沿主边（树边）到达 u 的路径对应的字符串，v 为 q 在 SAM 上任意游走到达某一个终止状态的路径对应的字符串。
:::info[两者存在性]
前者的存在性基于生成树是容易证明的，对于后者，依照其 \operatorname{longest} 在原字符串之后的字符增加即可，一定能够走到一个最终状态。
这里只需保证一个后缀对应一条次级边，一条次级边可能对应多个后缀。
:::
:::info[注]
笔者并不理解 OI-Wiki 上有关这一段的证明，首先是出现了一个未定义的完整的转移 （可能是指连续的转移，或主边），又限制 v 只由完整的转移组成，这样存在性就并不好说明甚至可能是有问题的。
:::
此时 (p,q) 是后缀 \alpha 对应的路径上首个 次级边，同时，\alpha 对应的路径是唯一的。
故次级边数量不超过后缀数量，空串显然可以只通过主边得到，则不超过 n 。
此时已经可以分析到 \le 3n 了，更精细的分析可以分析到 \le 3n-4 。
引理
引理：x 到 y 有一条主边，则 |\operatorname{SC}(y)|=|\operatorname{SC}(x)|-k+1 ，其中 k 为 \operatorname{SC}(x) 到 \operatorname{SC}(y) 中次级边的数量。
证明：来研究 \operatorname{SC}(y) 和 \operatorname{SC}(x) 之间的关系。
假设 x\xrightarrow{a}y ，则 \operatorname{SC}(y) 中的每一个状态 z 都有至少一个进入 该状态的 a 转移边（除 t_0 ），
进一步，\forall z\in \operatorname{SC}(y) ，都恰有一条 a 转移边满足：起点 w\in\operatorname{SC}(x) 且是一条主边。
:::info[证明]{open}
从字符串的角度去考虑，把 z 代表的子串的最后一个字符抹去，则一定表现为 x 的代表的子串的后缀，则 w\in\operatorname{SC}(x) ；特别地，把 \operatorname{longest}(z) 的最后一个字符抹去，则一定有 \operatorname{len}(w)+1=\operatorname{len}(z) ，是一条主边。
注：\operatorname{end-set} 之间的真包含关系构成后缀链接树；不同状态之间，\operatorname{end-set} 的关系只有真包含或相离。证明参考 OI-Wiki 关于 \operatorname{endpos} 的部分。
:::
反过来，\forall w\in\operatorname{SC}(x) ，有：存在一条 a 转移边终点为 \operatorname{SC}(y) 中的状态。
:::info[证明]
同样是从字符串角度和 \operatorname{end-set} 的包含关系考虑。
由包含关系 $\forall w\in\operatorname{SC}(x)\setminus\{x\},\operatorname{end-set}(x)\subsetneq\operatorname{end-set}(w)$ 和 $\forall z\in\operatorname{SC}(y),\operatorname{end-set}(y)\subseteq \operatorname{end-set}(z)$，
有 $\forall w\in\operatorname{SC}(x),\exist z\in\operatorname{SC}(y),\exist r\in\operatorname{end-set}(w)\land r+1\in\operatorname{end-set}(z),S[r+1]=a$。
通俗而言就是考虑字符串中相同的前缀，截取其不同长度的后缀，往后添加字符。
:::
除去主边的对应关系之外，剩下的就是次级边了。那么 $|\operatorname{SC}(x)|-(|\operatorname{SC}(y)|-1)=k$ 是自然成立的，其中 $-1$ 即表示除去 $t_0$。
## 复杂度证明
至此，我们就能够证明重定向的总复杂度为 $O(n)$：
下面的 $\operatorname{SC}$ 是针对**插入当前字符后**的后缀链接树的。
流程的情况三中，不会重定向任何一条主边，若出现主边，则其终点一定不为 $nq$，因为 $\operatorname{len}(p)+1=\operatorname{len}(nq)$ 已经成立了，$\operatorname{SC}(p)$ 中的 $\operatorname{len}$ 只会单调递减。
则重定向的总边数 $\le k+1\le |\operatorname{SC}(p)|-|\operatorname{SC}(nq)|+2$，这里 $+1$ 表示 $p\rightarrow nq$。
又有：$|\operatorname{SC}(nq)|=|\operatorname{SC}(now)|-1,|\operatorname{SC}(p)|=|\operatorname{SC}(last)|-k^\prime$，其中 $k^\prime$ 表示在 $p$ 之前向 $np$ 连的边数。
则重定向的总边数 $\le|\operatorname{SC}(last)|-|\operatorname{SC}(now)|+3-k^\prime$。
则单次操作时间（除转移边复制）复杂度为：$O(|\operatorname{SC}(last_i)|-|\operatorname{SC}(now_i)|)+O(1)$。
:::info[注]
扩展到情况一、二自然也是成立的，不妨自行检验。
这里还有一点提示是，复杂度是均摊的，
$|\operatorname{SC}(last_i)|-|\operatorname{SC}(now_i)|\ge|\operatorname{SC}(p)|-|\operatorname{SC}(nq)|\ge k-1\ge -1$。
:::
求和：$O(1)$ 项累积为 $O(n)$，$\sum_{i=1}^n|\operatorname{SC}(last_i)|-|\operatorname{SC}(now_i)|\le0$，还有转移边复制，其总量不超过转移数，为 $O(n)$。
于是，总时间复杂度为 $O(n)$，总空间复杂度为 $O(n|\Sigma|)$，瓶颈在存储转移边（相当一部分是不存在的）。
:::info[注]
笔者没有看懂 OI-Wiki 上利用 $\operatorname{longest}(fa(fa(last)))$ 单调的证明方法，疑似省掉了若干步骤？
:::
# 实现
:::info[关于 map 空间]
理论上而言，使用 `map` 的空间开销是线性的，然而，在 $|\Sigma|=26$ 时，其表现并不佳。统计关于**转移边**的开销如下：
用结构体内部开数组的方式，每个结点开销约为 $(26+1)\times 4=108$ 字节（$+1$ 表示额外开一个变量压位存储有哪些转移边存在）。
开一个空的 `map` 的空间开销一般为 $48$ 字节，除最后一个结点外，每个结点至少有一条出边，而 `map` 中一个结点的结构体开销一般为 $40$ 字节，此时已经有 $88$ 字节了。
此外，`map` 可能还有哨兵开销和分配开销，实际开销基本无优化甚至是劣化。
:::
现在只需要考虑 $O(1)$ 访问某条转移边，可以选择每个结构体开一个大小为 $|\Sigma|$ 的数组，或者用哈希表维护。
而且后者可以做到线性空间，但是有被卡的风险。（复杂度可能会和 $|\Sigma|$ 相关）
在一些题目中，$|\Sigma|=26$，且要求能够访问最大转移边和最小转移边，可以利用 `int` 压位存储哪些边存在，`builtin` 家族访问。
:::info[注]{open}
经过测试，使用 `31^__builtin_clz(x)` 求 $\log$ 可以做到 $2\times 10^8$ 次求解用时 220ms。效率较高，可以接受。
:::
下面是模板题的两种实现，其中哈希表实现参考了[这份记录](https://www.luogu.com.cn/record/275150251)的实现。
:::info[哈希表]
开放寻址法。
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 1000005
char S[N];
int n,nqcnt,hashsiz,fa[N<<1];
int siz[N<<1],len[N<<1],qp[N<<1];
pair<int,int>table[N*12];//键值对
long long res;
//12=3*2*2，与字符集无关，但实际表现空间上是常数优化
struct node{//哈希表信息：pos 总空间起始位置，up 大小上限
int pos,up,cnt,to;//cnt 当前大小，to 是压位的出边集合
inline void init(){
cnt=0,to=0,up=2,pos=hashsiz+1,hashsiz+=up;
}
inline void Copy(){//复制的至少 1/4 是有用的，常数可控
int x=pos;
pos=hashsiz+1,hashsiz+=up;
for(int i=0;i<up;i++) table[pos+i]=table[x+i];
}
inline void change(int c,int v){//把字符 c 位置修改为 v
for(int i=c&up-1;;i=i+1&up-1){
if(table[pos+i].first==c){
table[pos+i].second=v;break;
}
}
}
inline void rebuild();
inline void ins(int c,int v);
inline int find(int c){
for(int i=c&up-1;table[i+pos].first;i=i+1&up-1){
if(table[i+pos].first==c) return table[i+pos].second;
}
return 0;
}
}AM[N*2];
inline void extend(int c,int np){
int p=np-1;
len[np]=len[p]+1,siz[np]=1,AM[np].init();
for(;~p&&((~AM[p].to>>c)&1);p=fa[p]){
AM[p].ins(c,np),AM[p].to|=1<<c;
}
if(p==-1) return;
int q=AM[p].find(c),nq;
if(len[q]==len[p]+1) return fa[np]=q,void();
AM[nq=++nqcnt]=AM[q],AM[nq].Copy(),fa[nq]=fa[q];
len[nq]=len[p]+1,fa[q]=fa[np]=nq;
for(;~p&&AM[p].find(c)==q;p=fa[p]) AM[p].change(c,nq);
}
inline void cmax(long long &a,long long b){(a<b)&&(a=b);}
int main(){
#ifdef LOCAL
freopen("2.in","r",stdin);
#endif
n=fread(S+1,1,N-4,stdin);
while(!islower(S[n])) n--;//剔除不可见字符
nqcnt=n,fa[0]=-1,AM[0].init();
for(int i=1;i<=n;i++) extend(S[i]-'a'+1,i); //注意不要有 0
int head=1,tail=1;AM[0].cnt=998244353;
for(int i=1;i<=nqcnt;i++) AM[i].cnt=0;
for(int i=1;i<=nqcnt;i++) AM[fa[i]].cnt++;
for(int i=1;i<=nqcnt;i++){
if(AM[i].cnt==0) qp[tail++]=i;
}
for(int u,f;head<tail;){
u=qp[head++],siz[f=fa[u]]+=siz[u];
if((--AM[f].cnt)==0) qp[tail++]=f;
if(siz[u]>1) cmax(res,1ll*siz[u]*len[u]);
}
printf("%lld",res);
return 0;
}
inline void node::ins(int c,int v){
if(cnt+1>(up>>1)) rebuild();
cnt++;
for(int i=c&up-1;;i=i+1&up-1){
if(table[i+pos].first==0){
table[i+pos]={c,v};break;
}
}
}
inline void node::rebuild(){//重建，这里不建议简单复制
int u0=up,x=pos;
pos=hashsiz+1,up<<=1,hashsiz+=up,cnt=0;
for(int i=0;i<u0;i++){
if(table[x+i].first){
ins(table[x+i].first,table[x+i].second);
}
}
}
```
:::
:::info[数组]
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 2000005
#define ctz(x) __builtin_ctz(x)
struct node{
int ch[26],to;
inline void Copy(const node &f){//复制边信息
for(int t=f.to,x;t;t-=1<<x) x=ctz(t),ch[x]=f.ch[x];
to=f.to;
}
}AM[N];//两倍空间
char S[N];
int nqcnt,n,bfn[N];
int fa[N],len[N],siz[N];
long long res=0;
inline void extend(int i,int c){
int p=i-1,np=i;len[np]=len[p]+1;
for(;~p&&!AM[p].ch[c];p=fa[p]) AM[p].ch[c]=np,AM[p].to|=1<<c;
if(p==-1) return;//fa 其实为 0
int q=AM[p].ch[c],nq;
if(len[q]==len[p]+1) return fa[np]=q,void();
AM[nq=++nqcnt].Copy(AM[q]),fa[nq]=fa[q];
len[nq]=len[p]+1,fa[np]=fa[q]=nq;
for(;~p&&AM[p].ch[c]==q;p=fa[p]) AM[p].ch[c]=nq;
}
inline void cmax(long long &a,long long b){(a<b)&&(a=b);}
int main(){
fread(S+1,1,N-5,stdin),n=strlen(S+1);
while(!islower(S[n])) n--;
nqcnt=n,fa[0]=-1;
for(int i=1;i<=n;i++) extend(i,S[i]-'a');
for(int i=1;i<=nqcnt;i++) siz[len[i]]++;
for(int i=1;i<=n;i++) siz[i]+=siz[i-1];
for(int i=1;i<=nqcnt;i++) bfn[siz[len[i]]--]=i;
for(int i=1;i<=nqcnt;i++) siz[i]=i<=n;
for(int i=nqcnt,u;i>=1;i--){
u=bfn[i],siz[fa[bfn[i]]]+=siz[bfn[i]];
if(siz[u]>1) cmax(res,1ll*siz[u]*len[u]);
}
printf("%lld",res);
return 0;
}
```
:::
在 SAM 中，有一个常用的常数优化：用拓扑序代替 dfs。因为 $\operatorname{len}$ 在后缀链接树上单调，可以计数排序 $O(n)$ 求解出一个拓扑序。处理后缀链接树上一些信息时，就可以利用拓扑序循环解决。
但是，SAM 的线性写法在实际运行中效率优势并不显著，一方面是 SAM 的时间常数并不小（还会有一个计数排序），另一方面 `memcpy` 的方式常数较小，整体来看，比 $O(n|\Sigma|)$ 的写法像是一个常数优化。
# 关于广义 SAM
## 限制总长
采取在线做法，记 $n=\sum_ilen_i$ 表示总长。状态数、转移数、引理的证明同单串的情况。
复杂度证明中，新增内容也满足单次复杂度为：$O(|\operatorname{SC}(last_i)|-|\operatorname{SC}(now_i)|)+O(1)$。$now_i$ 的定义为该次插入字符返回给**下一步的 $last$**。
串之间将 $last$ 置为 $t_0$ 的操作不会使复杂度升高。则总复杂度同单串情况，时间复杂度 $O(n)$。
:::info[关于伪广义 SAM]
伪广义 SAM 的正确性存在某些问题，在此不讨论其时间复杂度，具体内容可以参考[此题解 by](https://www.luogu.com.cn/article/pm10t1pc) [辰星凌大佬](https://www.luogu.com.cn/user/110985)。
:::
## 给定字典树
给出的是一棵 Trie 树的情况（总长不可接受）较为复杂。状态数和引理的正确性不受影响，但是转移数可以达到 $O(|T||\Sigma|)$，则时空复杂度均不低于 $O(|T||\Sigma|)$。
:::info[构造]{open}
如何卡满？考虑构造这样一棵扫帚型的字典树：先放 $|T|-|\Sigma|$ 个 $a$，造出一条长链，剩下的结点在链底端加入 $|\Sigma|$ 种字符，构造出来的转移数就是 $O(|T||\Sigma|)$。
:::
字符集极大（和 $|T|$ 同阶）时，时空复杂度均不可接受，目前无前途。
:::info[注]
由于增加的是转移数，所以 `map` **并不能**将时间复杂度优化到 $O(|T|\log{|\Sigma|})$。这也是不理解复杂度省略字符集的行为的原因之一。
:::
### 在线方法
利用引理，可以证明时间复杂度为 $O(|T||\Sigma|+G(T))$，其中 $|T|$ 为 Trie 的结点数，$G(T)$ 为 Trie 所有叶子的深度之和。
具体地，把所有字符串剥离出来，像给定总长一样处理，即可做到上述复杂度。需要注意的是：处理相同前缀时，会有大量的重合，有大量插入是没有新建结点的。
:::info[注]
也可以从离线 dfs 的方法去考虑。
:::
### 离线方法
离线 dfs 和在线方法相似，具体内容可以参考“伪广义 SAM”中给出的链接。
然而，关于如何证明离线基于 bfs 构造的复杂度为 $O(|T||\Sigma|)$，笔者并没有找到有关的较为详细的证明。
在 2015 年国家集训队论文中，有提到“只有固定的子串组合会使我们需要暴力修改转移函数”，但也没有给出较详细的证明。
:::info[注]{open}
在 UOJ 用户群中，有一位退役大佬回复：Ta 在役的时候也问过多次如何证明，然而无人回复。
如果有大佬了解证明，或者找到了有关论文，欢迎交流。在此提前拜谢。
:::