后缀自动机（SAM）学习笔记
后缀自动机（SAM）学习笔记
更好的阅读体验1
更好的阅读体验2
注：文中所有字符串位置从1开始
注：若无特别标出，文中所有子串均为可空子串
注：空串在文中用下划线_表示
注：初始状态与空串代表的状态意义相同
注：文中状态，结点与
注：图中实线表示DAWG边，虚线表示后缀link。
SAM基础知识
引入
SP1811 LCS - Longest Common Substring
题意：求两个字符串的最长公共子串长度。
数据范围：
- 我会暴力！
-
-
-
-
-
-
-
- 总复杂度
O(n^4)
- 总复杂度
- 我会暴力优化！
-
-
-
-
-
- 总复杂度
O(n^3)
- 总复杂度
- 我会二分+哈希！
-
- 过程略
-
- 总复杂度
O(n\log^2 n)
- 总复杂度
前两个算法不可以通过本题，二分哈希虽然能通过，但数据加强就也无能为力了。
我们需要一个更优秀的算法——最好有线性复杂度，它就是后缀自动机，又称SAM（Suffix AutoMaton）。
SAM的定义
SAM是一个能接受字符串所有后缀的最小DFA（确定性有限自动机），同时它其实也可以表示这个字符串的所有子串。
即可以理解为：SAM是一张DAG（其实这个定义不是特别准确，后面会讲），从SAM的起点开始走，可以通过一些边（相当于字符）进行转移，只有字符串的后缀才能到终止集合（注意，终点不止一个，但起点只有一个），且SAM的结点数是最少的。
学SAM需要知道的
结束位置集合endpos
我们定义
举个例子，对于字符串
endpos 等价类
我们定义
还是上面这个例子：对于字符串
后缀link
对于一个
这里再举个例子吧，对于字符串
终止集合&终止链
对于每一个后缀形成的
Parent Tree
根据后缀link将所有
比如，根据字符串
DAWG（Direcged Acyclic Word Graph）
定义DAWG为能表示字符串所有后缀的图，其中每一个结点都是一个
形成DAWG的DAWG边带权，表示某个
DAWG的构造会在后面讲到，这里用上面的字符串
其实DAWG和Parent Tree是共用一套结点的，只是边不一样而已。
连续的转移
设
SAM的性质
性质1：对于两个非空子串a,b （|a|\leqslant|b| ），a\in suffix(b)\Leftrightarrow endpos(b)\subseteq endpos(a) ，a\notin suffix(b)\Leftrightarrow endpos(a)\cap endpos(b)=\varnothing
这里证的有些问题，之后再补上。
性质2：将一个endpos 等价类的所有字符串按长度从大到小排序后，每一个字符串都是其前面的字符串的后缀，且这些后缀是连续的（即长度严格递增）
考虑
然后我们设
因此，我们证明了一个
性质3：endpos 等价类的级别为O(n)
考虑一颗表示长度为
这个不懂没关系，在证明复杂度的时候会再次提及（以另一种方式）。
性质4：若存在u 连向v 的后缀link，那么minlen(u)=maxlen(v)+1
上面讲过，后缀link可以看做分割关系，即被连向的状态分割成所有连向它的状态（注意，某些
有了这个性质，我们可以在构造SAM的时候少保存一些信息。
性质5：从初始状态到任意状态，有且仅有一条完全由连续转移组成的路径到达
这个很显然，因为跳连续转移意味着在后面添加字符，如果有两条完全由连续转移组成的路径，那么这两条路径一定是重合的。
SAM的构造
SAM一般指Parent Tree与DAWG一整套结构，下面我们对这两个结构的构造进行讲解：
DAWG
DAWG可以用一种叫做增量法的方式进行在线构造：
首先定义变量：
由于是在线构造，因此我们考虑每次都加入字符
我们考虑哪些点需要更新，由于要让所有的后缀被表示出来，因此只需要之前的最长后缀代表的
那么我们首先新建一个结点
看一种情况：
我们需要将终止链上的状态连向
但是远远没有这么简单，在下图中，
首先还是新建状态
此时，我们需要分类讨论一下：
如果
否则，
此时我们需要克隆出一个新状态
考虑如何更新各个经过修改的结点的后缀link：
因为存在
同理，因为
同时，由于
最后，我们遍历剩余的终止链，由于
当然，这条终止链上可能还有其他的结点，它们如果不指向状态
代码（原则：理解性默写）：
int extend(int last,int x){
int now=++tot,pos=last,tmp,cln;
len[now]=len[last]+1;
while(pos!=0&&nxt[pos][x]==0)
nxt[pos][x]=now,pos=link[pos];
if(pos==0){
link[now]=1;
return now;
}
tmp=nxt[pos][x];
if(len[tmp]==len[pos]+1){
link[now]=tmp;
return now;
}
cln=++tot;
for(int i=1;i<=26;i++)
nxt[cln][i]=nxt[tmp][i];
len[cln]=len[pos]+1;
link[cln]=link[tmp],link[tmp]=link[now]=cln;
while(pos!=0&&nxt[pos][x]==tmp)
nxt[pos][x]=cln,pos=link[pos];
return now;
}主函数内，维护一下
cin>>s;
n=s.size(),s=" "+s;
last=++tot;
for(i=1;i<=n;i++)
last=insert(s[i]-96);Parent Tree
Parent Tree很容易建，只需要把所有后缀link连边就好了。（注意，为了让空串代表的状态为根结点，因此需要反着建边）
代码：
for(i=2;i<=tot;i++)
add(link[i],i);DAWG和Parent Tree的差别与联系
- DAWG的结点和Parent Tree中的的结点相同。 由定义可得。
- 跳DAWG边意味着在后面添加一个字符，跳后缀link意味着在前面减少若干个字符。
由DAWG边的定义，第一句话显然。
由后缀link的定义，我们知道存在后缀link的两条状态的
endpos 等价类是包含关系，即存在后缀关系，那么跳后缀便意味着在前面减少若干个字符。 - 在后面添加一个字符一定会跳DAWG边，而在前面减少若干个字符不一定会跳后缀link。
由DAWG边的定义，第一句话显然。
因为每一个结点表示的是一个
endpos 等价类，所以可能代表多个串，因此在前面减少若干个字符不一定会跳后缀link。 - DAWG是一个DAG（Directed Acyclic Graph，有向无环图），而Parent Tree是一棵树。 因为跳DAWG边长度会增加，所以长度只增不减，一定无法形成环，因此DAWG是一个DAG。 除空串外，所有状态都会有一条后缀link指向其他的状态，因此Parent Tree是一棵树。
SAM的正确性证明
因为每一次添加字符一定会让当前的终止链中所有结点（包括空串代表的状态）存在一条边权为这个字符的DAWG边，所以SAM一定可以表示出字符串的所有后缀，进一步，也可以表示字符串的所有子串。（因为走后缀的时候一定会走过后缀的前缀，而子串可以理解为后缀的前缀）
SAM的复杂度证明
这里假定字符集大小是常数，那么SAM的复杂度为
SAM的状态数是O(n) 的
按照建SAM的过程，有一个初始状态（空串），第一次添加状态和第二次添加状态的时候不可能进行克隆，后面每一次都有可能进行克隆，因此总状态数最多为
实际上，存在状态数达到上限的情况：
因为SAM中所有结点是这个串所有的
SAM的转移数是O(n) 的
我们构造以空串代表的状态为根的最长路径生成树，那么这个生成树上的转移一定是连续的转移（否则一定找得出一条更长的路径来代替树上不连续的转移）。我们称在最长路径生成树上的转移为树边，其他的转移为非树边。因此有且仅有一条路径可以通过树边从根走到任意结点。
我们考虑每一条非树边
得到了非树边和路径是单射的后，我们考虑这些路径的含义：因为这些路径都是从空串代表的状态到终止状态的路径，因此每一条路径都代表字符串的一个后缀，且完整串代表的后缀一定不在这些路径上（因为完整串代表的路径上的转移一定都是连续的，而由SAM的性质“初始状态到某一状态连续转移组成的路径一定只有一条”得完整串代表的路径一定在最长路径生成树上），所以非树边的个数为真后缀（即非完整串的后缀）代表的路径的个数，因此非树边最多有
最长路径生成树的边数（即转移数）为点数减一，点数最多为
实际上，SAM的转移数无法到达上界，因为如果状态数达到了上界，那么串一定是
构建SAM的时间复杂度是O(n) 的
我们看SAM的构建代码：
int extend(int last,int x){
int now=++tot,pos=last,tmp,cln;
len[now]=len[last]+1;
while(pos!=0&&nxt[pos][x]==0)
nxt[pos][x]=now,pos=link[pos];
if(pos==0){
link[now]=1;
return now;
}
tmp=nxt[pos][x];
if(len[tmp]==len[pos]+1){
link[now]=tmp;
return now;
}
cln=++tot;
for(int i=1;i<=26;i++)
nxt[cln][i]=nxt[tmp][i];
len[cln]=len[pos]+1;
link[cln]=link[tmp],link[tmp]=link[now]=cln;
while(pos!=0&&nxt[pos][x]==tmp)
nxt[pos][x]=cln,pos=link[pos];
return now;
}首先，里面非循环的复杂度是
然后，我们看向
- 第
1 个循环：我们将终止链上所有没有c 字符转移的状态添加一个转移到now （即每循环到一个pos 都会添加一个转移），由于转移数不会减少，转移数是O(n) 的，所以这个循环总复杂度一定是O(n) 的。 - 第
2 个循环：同样的，cln 一开始没有转移，只有第2 个循环才会给cln 新的转移，由于转移数是O(n) 的，所以这个循环总复杂度也是O(n) 的。 - 第
3 个循环，之前证明证错了，希望有一个巨巨可以帮我证一证QAQ
故，我们证明了一个很美妙的性质——SAM的时间复杂度是
SAM的复杂度优化
上面，我们证明了SAM的复杂度是
- 对字符集进行离散化（显然），
|\Sigma| 优化为O(n) 级别。 - 用
map 对nxt 的存储与复制进行加速：考虑nxt 只有赋值和复制两个操作，我们可以通过map 优化nxt 的赋值操作，使字符集大小变成\log 级别的，即复杂度优化成O(n\log|\Sigma|)
代码很简单（离散化不给出）：
map<int,int>nxt[maxn];
int extend(int last,int x){
int now=++tot,pos=last,tmp,cln;
len[now]=len[last]+1;
while(pos!=0&&nxt[pos][x]==0)
nxt[pos][x]=now,pos=link[pos];
if(pos==0){
link[now]=1;
return now;
}
tmp=nxt[pos][x];
if(len[tmp]==len[pos]+1){
link[now]=tmp;
return now;
}
cln=++tot;
nxt[cln]=nxt[tmp];
len[cln]=len[pos]+1;
link[cln]=link[tmp],link[tmp]=link[now]=cln;
while(pos!=0&&nxt[pos][x]==tmp)
nxt[pos][x]=cln,pos=link[pos];
return now;
}SAM的应用
作者只做过一些SAM的题，因此SAM的应用总结不全，就这样看看吧（
1.处理各种字符串信息
SAM可以很简单地处理各种关于子串长度，子串出现次数等信息。
子串出现次数：对于某个状态，它的出现次数可以在Parent Tree上记一下数（具体地，对于每一次
void dfs(int x){
size[x]=tag[x];
for(int i=start[x];i;i=then[i]){
int y=to[i];
dfs(y);
size[x]+=size[y];
}
}（其中
子串长度：某个状态
似乎没有什么要放的代码，凑个数QAQ子串长度出现次数：对于某个状态，区间修改一下子串长度区间，一般可以差分做。
cnt[len[link[x]]+1]++,cnt[len[x]+1]--;
for(i=1;i<=n;i++)
cnt[i]+=cnt[i-1];P3804 【模板】后缀自动机 (SAM)：求所有出现次数不为
P5341 [TJOI2019]甲苯先生和大中锋的字符串：求恰好出现
CF802I Fake News (hard)：求所有子串的出现次数平方和，直接统计就可以了。
CF123D String：求所有子串的出现次数乘(出现次数
SP8222 NSUBSTR - Substrings：给定长度为
2.求本质不同子串个数
- 方法
1 ：Parent Tree上计一下数。 - 方法
2 ：DAWG上计算路径个数。 - 方法
3 ：（在线）每一次加入一个串都将新建的结点包含的子串个数统计到答案中（即len_{now}-len_{link_{now}} ）。 - 应该按不同情况选择不同的方法。
方法
void dfs(int x){
size[x]=len[x]-len[link[x]];
for(int i=start[x];i;i=then[i]){
int y=to[i];
dfs(y);
size[x]+=size[y];
}
}方法
void dfs(int x){
if(ans[x])
return ;
ans[x]=1;
for(int i=1;i<=26;i++)
if(nxt[x][i]){
dfs(nxt[x][i]);
ans[x]+=ans[nxt[x][i]];
}
}方法
for(i=1;i<=n;i++){
last=extend(last,s[i]);
ans+=(len[last]-len[link[last]]);
}SP694 DISUBSTR - Distinct Substrings求本质不同子串个数。
SP705 SUBST1 - New Distinct ：求本质不同子串个数，是上一题加强版。
P2408 不同子串个数：求本质不同子串个数。
P4070 [SDOI2016]生成魔咒：求本质不同子串个数，离散化+map优化。
SP32951 ADASTRNG - Ada and Substring：求某个字母开头本质不同子串个数。
#6071. 「2017 山东一轮集训 Day5」字符串：求多个串可空子串拼接后不同子串个数，对每个串建SAM，然后用子序列自动机把DAWG拼接起来，形成的新DAG有个美妙的性质：它上面的路径对应着所有新字符串的子串。这样，我们就只需要在上面计算路径数量就可以了。
P6139 【模板】广义后缀自动机（广义 SAM）：求多串本质不同子串，建广义SAM后直接算
3.匹配子串/匹配循环同构
我们要在
可以考虑不断让这个串进行两个操作：向前增加字符来进行匹配，将无法继续匹配的字符丢弃（以匹配后面的字符）。
我们在学习笔记辨析过Parent Tree和DAWG的差异与联系，在这里派上了用场：
如何在后面增加字符：跳一个为这个字符的DAWG边，一定让你恰好增加了一个字符。
如何在前面丢弃字符：每一次丢弃字符都暴力跳后缀link，直到到根结点或者存在当前匹配字符的DAWG边。由后缀link的定义可以知道跳后缀link是让你的
因为每个状态最多遍历一遍，所以复杂度是
int now=1,l=0;
for(i=1;i<=n;i++){
while(now!=0&&nxt[now][s[i]]==0)
now=link[now],l=len[now];
if(nxt[now][s[i]])
now=nxt[now][s[i]],l++;
......
}循环同构：
循环同构的匹配和普通串的匹配差不多，你只需要破环为链就可以了。（不过有一点要注意，如果匹配的长度大于该字符串的长度，那么需要强制失配）
破环为链就不需要代码了吧QAQCF235C Cyclical Quest：给定
4.最小表示法
最小表示法：求字符串字典序最小的循环同构
很简单，只需要倍长一下（因为要破环为链），建好SAM，然后在DAWG上贪心走字典序更小的边就可以了（也可以用
放的是第二种做法。
int now=1;
for(int i=1;i<=n;i++){
int x=nxt[now].begin()->first;
printf("%d ",x);
i=nxt[i][x];
}P1368 工艺 /【模板】最小表示法：板子题
5.求k 大子串
- 本质不同
k 大子串：首先每个点点权为1 ，然后在DAWG上计数，得到每个状态能达到的状态点权之和。搜索的时候判断一下，如果k 大于点权之和，我们就不走这个状态，然后把k 减一下，否则就走这个状态（因为这个状态能到达的串数量大于等于k ，那么第k 大一定包含在里面）。 - 位置不同
k 大子串：在Parent Tree上求出每个状态出现次数，作为点权，转化为上面的情况。
本质不同
void getcnt(int x){
if(cnt[x])
return ;
cnt[x]=x==1? 0:1;
for(int i=1;i<=26;i++){
int y=nxt[x][i];
if(y==0)
continue;
getcnt(y);
cnt[x]+=cnt[y];
}
}
void query(int x,int k){
if(k<=0)
return ;
for(int i=1;i<=26;i++){
int y=nxt[x][i];
if(y==0)
continue;
if(k>cnt[y]){
k-=cnt[y];
continue;
}
printf("%c",i+96);
query(y,k-1);
return ;
}
}位置不同
void getsize(int x){
size[x]=tag[x];
for(int i=start[x];i;i=then[i]){
int y=to[i];
getsize(y);
size[x]+=size[y];
}
}
void getcnt(int x){
if(cnt[x])
return ;
cnt[x]=x==1? 0:size[x];
for(int i=1;i<=26;i++){
int y=nxt[x][i];
if(y==0)
continue;
getcnt(y);
cnt[x]+=cnt[y];
}
}
void query(int x,int k){
if(k<=0)
return ;
for(int i=1;i<=26;i++){
int y=nxt[x][i];
if(y==0)
continue;
if(k>cnt[y]){
k-=cnt[y];
continue;
}
printf("%c",i+96);
query(y,k-size[y]);
return ;
}
}P3975 [TJOI2015]弦论：求本质不同/位置不同的
SP7258 SUBLEX - Lexicographical Substring Search：求本质不同
6.求公共串
我们定义
bitset<maxn>end[maxn];
int extend(int last,int x){
......
end[now][t]=1;
......
}
void dfs(int x){
for(int i=start[x];i;i=then[i]){
int y=to[i];
dfs(y);
end[x]|=end[y];
}
for(int i=1;i<=n;i++)
if(end[x][i]==0)
return ;
ans=max(ans,len[x]);
}SP1811 LCS - Longest Common Substring：求两串公共串，也可以用第二个串在第一个串上跑匹配。
SP1812 LCS2 - Longest Common Substring II：求多串公共串
SP10570 LONGCS - Longest Common Substring：多组数据，求多串公共串
P5546 [POI2000]公共串：求多串公共串
P2463 [SDOI2008]Sandy的卡片：求所有串的相同段（其中相同段的定义为这一段统一加上某个数就会变成另一端），差分一下就是求公共串的裸题
7.求后缀的lcp /前缀的lcs
有些题目需要求SAM中
- 方法
1 ：直接用二维数组endpos_{i,j} 表示状态i 的endpos 是否包括j ，在Parent Tree 上暴力合并，复杂度为O(n^2) 。 - 方法
2 ：用bitset 记录endpos ，然后在Parent Tree上合并endpos 就可以了，好写，复杂度优化为O(\frac{n^2}{\omega}) 。 - 方法
3 ：用动态开点线段树记录每一个串的endpos ，然后再Parent Tree 上跑线段树合并（具体地，就是把每个位置i 都记录一个根结点rt_i ，以这个根结点建立动态开点线段树，修改直接单点修改结束的位置），复杂度为O(n\log n) ，缺点是炸空间。
注：SAM上线段树合并，经常和树上倍增搭配在一起，就是屑上加屑。
CF1037H Security：给定
P4094 [HEOI2016/TJOI2016]字符串：SAM+线段树合并+二分答案
CF666E Forensic Examination，广义SAM+线段树合并+子串匹配+树上倍增