「笔记」后缀自动机 new

2024-01-21 11:42:10

一、一些概念
- 1. Endpos 集合
- 2. Parent Tree
二、后缀自动机
三、简单应用
四、广义 SAM
- 1. 离线做法
- 2. 在线做法

之前学过现在忘光了呜呜。2021.12.30 重写，好像写的有点乱。

一、一些概念

后缀自动机（SAM）是可以且仅可以接受一个母串 \(S\) 的后缀的 DFA。SAM Drawer。

1. Endpos 集合

子串的结束位置集合。比如 banana 中，\(\text{endpos}(\text{ana})=\{4,6\}\)。

对于两个子串 \(t_1,t_2\)，若 \(\text{endpos}(t_1)=\text{endpos}(t_2)\)，则 \(t_1,t_2\) 属于一个 \(\text{endpos}\) 等价类。

对于非空子串 \(t_1,t_2\,(|t_1|\leq |t_2|)\)：

若 \(t_1,t_2\) 属于同一个 \(\text{endpos}\) 等价类，则 \(t_1\) 在 \(S\) 中每次出现，都是以 \(t_2\) 的后缀形式存在。
若 \(t_1\) 为 \(t_2\) 的后缀，则 \(\text{endpos}(t_2)\subseteq \text{endpos}(t_1)\)；否则 \(\text{endpos}(t_2)\cap \text{endpos}(t_1)=\varnothing\)。
一个 \(\text{endpos}\) 等价类中的串为 某个前缀 的 长度连续的后缀。
\(\text{endpos}\) 等价类的个数为 \(\mathcal{O}(n)\) 级别。这个在后面会叙述。

根据合并等价类的思想，我们将 \(\text{endpos}\) 集合完全相同的子串合并到同一个节点。这样一来大大优化了时间和空间复杂度。SAM 的每个节点都表示一个 \(\text{endpos}\) 等价类。

2. Parent Tree

先继续谈谈 \(\text{endpos}\) 集合。

我们知道，SAM 里的每个节点都代表了一堆 \(\text{endpos}\) 集合相同的子串。容易发现，对于越短的子串，其 \(\text{endpos}\) 集合往往越大。更具体地，若 \(t_1\) 为 \(t_2\) 的后缀，则 \(|\text{endpos}(t_1)|\geq |\text{endpos}(t_2)|\)，当且仅当取得等号时，\(t_1,t_2\) 会被压缩到同一个节点中。

而对于 \(t_2\) 的每一个后缀，一定有一个分界点，使得对于长度 \(\geq\) 该分界点的后缀，它和 \(t_2\) 的 \(\text{endpos}\) 集合相同；而长度 \(<\) 该分界点的后缀，因为短，所以有机会可以在 \(S\) 中出现更多次，\(\text{endpos}\) 集合会更大，于是就和 \(t_2\) 分开了。因此，每个节点 \(p\) 中存储的一定是一堆长度连续的子串，且短的串是长的串的后缀。

对于 SAM 的每个节点都能找到一个这样的“分界点”，并且每个节点都对应了一个唯一的“分界点”。而如果 \(t_1\) 是 \(t_2\) 的一个后缀且没有和 \(t_2\) 分在一个节点中，那么 \(t_1\) 也可能成为别的子串的后缀（如 ab 既可以是 cab 的后缀，也可以是 zab 的后缀）。这样我们看到：长的串只能“对应”唯一的一个短的串，而短的串可以“对应”多个长的串，如果将“短的串”视为“长的串”的父亲，这就构成了一棵严格的树形结构。我们称为 Parent 树。

注意到短串对应的多个长串，它们的 \(\text{endpos}\) 集合无交（因为它们没有后缀关系，一个出现的位置另一个必然做不到也在这个位置出现）。对于一个父节点，其若干个儿子的 \(\text{endpos}\) 相当于将父节点的 \(\text{endpos}\) 分割成若干不相交的子集，最终会产生不多于 \(n\) 个叶节点。所以树的节点数也只有 \(\mathcal O(n)\)。

在 Parent 树中，一个节点 \(i\) 表示一个类，节点 \(i\) 的父亲记为 \(link_i\)（也被称为“后缀链接”）。显然 \(\text{endpos}(i)\subsetneq \text{endpos}(link_i)\)，\(link_i\) 代表的子串均为 \(i\) 子串的后缀。

设节点 \(i\) 对应对应的等价类中最长的子串为 \(\max(i)\)，最短的为 \(\min(i)\)。则 \(|\min(i)|=|\max(link_i)|+1\)，这个也很好理解。

Parent 树本质上是 \(\text{endpos}\) 集合构成的一棵树，体现了 \(\text{endpos}\) 的包含关系。

二、后缀自动机

1. 状态 & 转移

在 SAM 中我们把一个 \(\text{endpos}\) 等价类作为一个状态。

SAM 是由一个 Parent 树和一个 DAG 组成的，它们的状态集合相同。Parent Tree 和 DAG 是两种完全不同的边（一个是 \(link_x\)，一个是 \(ch_{x,c}\)），只是共用相同的节点。

当我们在 DAG 上从一个状态 \(x\) 走到 \(ch_{x,c}\)时，意味着在 \(ch_{x,c}\) 表示的部分字符串（“部分”是因为可以有多个点连向同一个点，接的 \(c\) 相同，但是起点不同）是的 \(x\) 后面 追加一个字符 \(c\) 得到的。在 SAM 的 DAG 上跑出来的串都是原串的子串。

比如 abab 的 SAM 长这样（Max 表示 \(|\max(p)|\)，size 表示 \(\text{endpos}\) 集合的大小，节点旁边写着的是 \(\text{endpos}\) 集合和所代表的字符串，黑色边表示 DAG 上的转移边，红色边是 Parent 树上的边）：

2. 构建

增量法，通过 \(S\) 的 SAM 求出 \(S+c\) 的 SAM。加入字符 \(c\) 后，子串只增加了 \(S+c\) 的后缀，已有的子串不受影响。

\(S+c\) 的某些后缀可能在 \(S\) 出现过，在 SAM 中有其对应的节点。

void insert(int c){
	int p=lst,x=lst=++tot;
	len[x]=len[p]+1;
	while(p&&!ch[p][c]) ch[p][c]=x,p=fa[p];
	if(!p){fa[x]=1;return ;}
	int q=ch[p][c],Q;
	if(len[q]==len[p]+1){fa[x]=q;return ;}
	Q=++tot,memcpy(ch[Q],ch[q],sizeof(ch[q]));
	fa[Q]=fa[q],len[Q]=len[p]+1,fa[q]=fa[x]=Q;
	while(p&&ch[p][c]==q) ch[p][c]=Q,p=fa[p];
}

lst 表示上一次添加的位置，fa[p] 表示 \(p\) 在 Parent 树上的父亲（也就是上面说的 \(link_p\)），len[p] 表示 \(|\max(p)|\)。

```
int p=lst,x=lst=++tot;
len[x]=len[p]+1;
while(p&&!ch[p][c]) ch[p][c]=x,p=fa[p];
```
前两句是比较显然的，\(p\) 为上一次添加的状态表示旧串，\(x\) 为现在的状态表示新串。\(p\) 肯定是上一次添加

第三句 p=fa[p] 就是在遍历后缀，高明之处在于对同一类后缀都可以统一处理，并且可以 压缩地遍历后缀。while(p&&!ch[p][c])，前者是为了不跳出根，对于后者，在 p=fa[p] 的过程中 \(p\) 表示的所有串（记为 \(s_p\)）始终是旧串的后缀，并且如果当前的 \(p\) 没有 ch[p][c]，说明 旧串中不存在 \(s_p+c\)，不难发现 \(s_p+c\) 是新串的后缀，而这又是第一次出现，因此 \(\text{endpos}(s_p+c)=\{n\}=\text{endpos}(S+c)\)，正确性是有保证的。

然而一旦发现 ch[p][c] 这个转移存在，说明 \(s_p+c\) 已经在旧串中出现了，那么 \(\text{endpos}(s_p+c)\neq \{n\}\)，直接连边有失妥当，我们需要对此进一步处理。
```
if(!p){fa[x]=1;return ;}
```
!p 就是跳出 SAM 而终止，也就是任意一个旧串的后缀 \(+c\) 都不曾在旧串中出现过。由于根状态（根表示的字符串是 \(\varnothing\)）是跳 \(fa\) 的必经之地，而这里都不存在 \(c\) 的转移，说明 \(c\) 在旧串中就没出现过。于是显然有 \(fa_x\gets rt\)。
```
int q=ch[p][c],Q;
```
走到这里了，说明前、前一句是因为发现一个存在的 \(c\) 转移而停下的，当前的 \(s_p+c\) 在旧串中出现过并且是新串的后缀。

那为什么选择 \(q\) 而不是 q'=ch[fa[p]][c] 呢（不继续跳后缀）？注意到 \(q'\) 在 Parent 树上必然是 \(q\) 的祖先，这些祖先在这一次 insert() 做完之后，其 \(\text{endpos}\) 也都增加了 \(n\)，情况本质相同。既然如此，对于这个 \(q\) 还需要多考虑什么呢？
```
if(len[q]==len[p]+1){fa[x]=q;return ;}
```
如果 \(|\max(q)|=|\max(p)|+1\)，等价于 \(\max(q)=\max(p)+c\)，说明 \(q\) 代表的所有串，以及 Parent 树上它的祖先代表的串，均为 \(S+c\) 的后缀。后缀的条件满足了，我们简单地让 \(\text{endpos}(q)\) 中多个 \(n\) 就行啦：\(fa_x\gets q\)，同时也满足了 \(\text{endpos}\) 的包含关系。

但是如果这个条件不成立，意味着 \(q\) 中存在一个比 \(\max(p)\) 更长的子串（因为 \(p\) 经过转移边 \(c\) 到 \(q\)，所以显然不会更短），这样更长的子串必然不会是新串的后缀，因为在不断遍历旧串后缀直到有出边 \(c\) 时，\(|\max(p)|+1\) 相当于是最长的在 \(S+c\) 里出现过的后缀。

“不会是新串的后缀”的话，会出现什么问题呢？首先可以肯定的是，\(n\notin \text{endpos}(q)\)。倘若我们令 \(fa_x\gets q\)，那么显然不符合 \(\text{endpos}\) 集合的分割性质，因为 \(\text{endpos}(x)=\{n\}\)。
```
Q=++tot,memcpy(ch[Q],ch[q],sizeof(ch[q]));
fa[Q]=fa[q],len[Q]=len[p]+1,fa[q]=fa[x]=Q;
while(p&&ch[p][c]==q) ch[p][c]=Q,p=fa[p];
```
解决方案？我们尝试将 \(q\) 这个状态拆分！

我们新建了一个状态 \(Q\)，作为拆分出来的状态，新建的 \(Q\) 满足 \(\text{endpos}(Q)=\text{endpos}(q)\cup \{n\}\)。在以后的 insert() 中，我们将使用这个新的含有 \(n\) 的 \(Q\) 而不是 \(q\)。

首先我们直接沿用 \(q\) 的所有转移，因为 \(Q\) 的 \(\text{endpos}\) 仅仅只是多了 \(n\)，除了这个 \(n\)，其他的子串后面加什么字符其实和原来的 \(q\) 并无大异。再看 \(len\)，因为 \(n\in\text{endpos}(q)\)，所以 \(\max(Q)\) 必然是新串的后缀，于是 len[Q]=len[p]+1。

最后是 \(fa\)。考虑到 Parent 树上祖先的 \(len\) 必然小于子孙，而 \(Q\) 又是 \(q\) 分拆出的状态，它们在 Parent 树上相邻。又因为 \(|\max(Q)|=|\max(p)|+1<|\max(q)|\)，那想必 \(Q\) 是 \(q\) 的父亲。这里的实现可以被认为是在 fa[q] 和 q 这条树枝上执行了一次类似于链表的插入，将 \(Q\) 置于它们之间，那么上面的代码就好理解了。

while(p&&ch[p][c]==q) ch[p][c]=Q,p=fa[p]; 中，ch[p][c]==q 是什么意思呢？对于一个存在 \(c\) 转移的一个 \(p\) 的祖先，可以肯定的是转移结果的 \(\text{endpos}\) 理应存在 \(n\)。然而我们发现这个结果是 \(q\)，而 \(n\notin \text{endpos}(q)\)，很明显违背了 Parent 树的性质，正好我们刚刚拆出一个 \(Q\)，而 \(n\in\text{endpos}(Q)\)，那直接将转移重定向到 \(Q\) 就行了。

3. 复杂度

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

Parent 树上最多只有 \(n\) 个叶节点，一个分叉点会合并至少两个子节点，Parent 树为完全二叉树时节点数最多，为 \(2n-1\) 个。
对于一个长度为 \(n\,(n\geq 3)\) 的字符串 \(S\)，它的 SAM 转移数 \(\leq 3n-4\)。

SAM 的 空间复杂度：

写成 int ch[N<<1][M]（其中 N 为状态数，M 为字符集大小）：空间 \(\mathcal O(n|\sum|)\)，查询时间 \(\mathcal O(1)\).
字符集较大时，可写成 map<int,int>ch[N<<1]，空间 \(\mathcal O(n)\)，查询时间 \(\mathcal O(\log|\sum|)\)。

构建 SAM 的 时间复杂度：均摊 \(\mathcal O(n)\)。

4. 模板

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

给出一个只包含小写字母的字符串 \(S\)，求 \(S\) 的所有出现次数不为 \(1\) 的子串的出现次数乘上该子串长度的最大值。

\(|S|\leq 10^6\)。

出现次数等价于 \(\text{endpos}\) 集合的大小。

上面提到 \(\text{endpos}\) 的分割关系构成一棵 Parent 树，记 \(sz_i=|\text{endpos}(i)|\)，首先不考虑信息丢失，那么 \(sz_i=\sum_{fa_j=i} sz_j\)。

接下来考虑丢失的那个（丢失是因为这个位置长度到顶了，无法往前扩展。这也暗示了最多只能丢失一个）。向前扩展导致长度到顶的只有一个位置，而这个必然是一个前缀，也就是说只有在一个可以表示主串一个前缀的状态的 \(\text{endpos}\) 才会拥有这样的元素。代码中只要在 insert() 中加上一句 sz[x]=1 即可。

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,M=30;
int n,lst=1,tot=1,ch[N][M],len[N],fa[N],sz[N];	//数组开两倍！注意 lst=tot=1
long long ans;
char s[N];
vector<int>v[N];
void insert(int c){
	int p=lst,x=lst=++tot;
	sz[x]=1,len[x]=len[p]+1;
	while(p&&!ch[p][c]) ch[p][c]=x,p=fa[p];
	if(!p){fa[x]=1;return ;}
	int q=ch[p][c],Q;
	if(len[q]==len[p]+1){fa[x]=q;return ;}
	Q=++tot,memcpy(ch[Q],ch[q],sizeof(ch[q]));
	fa[Q]=fa[q],len[Q]=len[p]+1,fa[q]=fa[x]=Q;
	while(p&&ch[p][c]==q) ch[p][c]=Q,p=fa[p];
} 
void dfs(int x,int fa){
	for(int y:v[x])
		if(y!=fa) dfs(y,x),sz[x]+=sz[y];
	if(sz[x]>1) ans=max(ans,1ll*sz[x]*len[x]); 
}
signed main(){
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++) insert(s[i]-'a');
	for(int i=2;i<=tot;i++) v[fa[i]].push_back(i);
	dfs(1,0),printf("%lld\n",ans);
	return 0;
}

为了减小常数，有时我们可以用“基数排序”代替树形 DP。

具体来说，在 DAG 或 Parent 树上 DFS 的操作，可以用拓扑序替代：\(len_p>len_{fa_p}\)（短串是长串的父亲），\(len_p<len_{ch_{p,c}}\)。

以在 Parent 树上 DFS 为例，我们按 \(len\) 值从小到大对节点排个序，就得到了整棵树从树根到树叶的拓扑序。把这个拓扑序倒过来，for 循环一遍，就相当于树形 DP 啦。

for(int i=1;i<=tot;i++) cnt[len[i]]++;
for(int i=1;i<=tot;i++) cnt[i]+=cnt[i-1];
for(int i=1;i<=tot;i++) id[cnt[len[i]]--]=i;

模板题完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+5,M=30;
int n,lst=1,tot=1,ch[N][M],len[N],fa[N],sz[N],cnt[N],id[N];	//数组开两倍！ 
long long ans;
char s[N];
vector<int>v[N];
void insert(int c){
	int p=lst,x=lst=++tot;
	sz[x]=1,len[x]=len[p]+1;
	while(p&&!ch[p][c]) ch[p][c]=x,p=fa[p];
	if(!p){fa[x]=1;return ;}
	int q=ch[p][c],Q;
	if(len[q]==len[p]+1){fa[x]=q;return ;}
	Q=++tot,memcpy(ch[Q],ch[q],sizeof(ch[q]));
	fa[Q]=fa[q],len[Q]=len[p]+1,fa[q]=fa[x]=Q;
	while(p&&ch[p][c]==q) ch[p][c]=Q,p=fa[p];
} 
signed main(){
	scanf("%s",s+1),n=strlen(s+1);
	for(int i=1;i<=n;i++) insert(s[i]-'a');
	for(int i=1;i<=tot;i++) cnt[len[i]]++;
	for(int i=1;i<=tot;i++) cnt[i]+=cnt[i-1];
	for(int i=1;i<=tot;i++) id[cnt[len[i]]--]=i;
	for(int i=tot,x;i>=1;i--) x=id[i],sz[fa[x]]+=sz[x];
	for(int i=1;i<=tot;i++)
		if(sz[i]>1) ans=max(ans,1ll*sz[i]*len[i]);
	printf("%lld\n",ans);
	return 0;
}

同时 SAM 还有一些有用的性质：

具体求 \(\text{endpos}\) 集合可以用线段树合并。
SAM 的每个节点表示的串的个数为 \(len_i-len_{fa_i}\)，表示的串互为后缀关系，长度在 \(len_{fa_i}+1\) 到 \(len_i\) 之间。
SAM 的 Parent 树中 \(fa_i\) 表示的串是 \(i\) 表示的串的后缀。反串 SAM 的 Parent 树就是后缀树。
- 正串的 SAM 维护的是原字符串所有前缀的后缀（可以考虑 SAM 增量法的构造过程）。那么同理，反串的 SAM，维护的就是所有后缀的前缀，可以得到所有后缀构成的 Trie（压缩后），即后缀树。
两个串最长公共后缀的长度，等于这两个串所代表的点在 Parent 上 LCA 的 \(len\) 值。这是因为，一个串对应节点的祖先节点都是它的后缀，且深度越大长度越长。

三、简单应用

1. 子串相关

从 DAWG 的起始节点 \(q_0\) 出发，每条路径唯一对应 \(S\) 的一个子串。因为 SAM 即能表示出所有子串，又不会出现两条不同路径表示同一个子串。

判断子串：判断 \(s\) 是否为 \(t\) 的子串。

对 \(t\) 建立后缀自动机 \(D_t\)（\(D_t\) 表示 \(t\) SAM 对应的 DAG），从根开始跑一遍 \(s\)。由于 \(D_t\) 中包含了 \(t\) 的所有子串，那么如果 \(s\) 在跑的过程中走到了空状态，那么说明不是 \(t\) 的子串。
子串出现次数

\(\text{endpos}\) 集合大小求出来就可以了。
本质不同的子串数
1. 离线做法
  
  \(s\) 本质不同的子串树即为 \(D_s\) 中根开始的不同路径数。
  
  设 \(f_x\) 表示从状态 \(x\) 开始的不同路径数，\(f_x=1+\sum_{ch(x,c)=y}f(y)\)。那么答案就是 \(f_{q_0}-1\)，复杂度线性。
2. 在线做法
  
  考虑到一个状态表示的子串长度连续，并且短串都是长串的后缀。那么 \(x\) 这个状态表示了 \([|\min(x)|,|\max(x)|]\) 这么多本质不同的子串。这些子串显然不能在其他状态中，于是所有状态包含的子串数之和记为答案：\(\sum_{x\in D_s}(len_x-len_{fa_x})\)。
  
  在实际维护时我们只要对于新建的那个 \(x\) 更新答案，不管 \(Q\) 是因为它只是分割了一个 \([|\min(Q)|,|\max(Q)|]\) 区间，并没有对答案产生贡献。复杂度显然也是线性。
本质不同子串总长
1. 离线做法
  
  在原来 \(f\) 的基础上设 \(g_x\) 为从状态 \(x\) 开始的不同路径总长，\(g_x=f_x+\sum_{ch(x,c)=y}g_y\)。
2. 在线做法
  
  动态维护 \(\large\sum_{x\in D_s}(\frac{len_x\times (len_x+1)}{2}-\frac{len_{fa_x}\times (len_{fa_x}+1)}{2})\) 即可。

2. 最长公共子串

两个串的最长公共子串：给定 \(s,t\)，求 \(s,t\) 的最长公共子串。

首先对 \(s\) 建立 SAM \(D_s\)，然后对于 \(t\) 的每一个前缀，我们希望这个前缀有尽量长的后缀可以匹配。换句话说，对于 \(t\) 的每一个位置，我们要找到这个位置结束的 \(s\) 和 \(t\) 的最长公共子串长度。

那么先把 \(t\) 放在 SAM 上跑，如果能走转移就走转移，否则我们慢慢从前面缩减长度，也就是跳 \(fa\)，直到存在一个当前字符的转移为止。

答案我们实时更新，每走一次转移取一次最大值即可。

复杂度仍为线性，因为我们维护 \(t\) 的起始位置和终止位置都在前移。
```
n=strlen(s1+1),m=strlen(s2+1),p=1;
for(int i=1;i<=n;i++) insert(s1[i]-'a');
for(int i=1;i<=m;i++){
	int c=s2[i]-'a';
	while(p&&!ch[p][c]) p=fa[p],l=len[p];
	if(ch[p][c]) p=ch[p][c],l++;
	else p=1,l=0;	//从起始节点重新匹配 
	ans=max(ans,l);
}
```

多个串的最长公共子串

首先我们对其中一个串建 SAM 其他的往上面跑，对于每个串，求出 \(mx_i\) 表示以状态 \(i\) 为结尾的最长匹配长度。然后记 \(mn_i\) 表示 \(mx_i\) 的历史最小值（因为是多个串，\(mn_i\) 才是所有串以 \(i\) 为结尾的最长匹配长度）。答案为 \(\max\{mn_i\}\)。

注意一个节点能被匹配，它在 Parent 树上的所有祖先都能被匹配。所以对于每一个节点 \(i\)，所以 \(mx_{fa_i}\gets \max(mx_{fa_i},mx_i)\)。别忘了确保 \(mn_i\leq len_i\)。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=30;
int t,k,n,lst=1,tot=1,ch[N][M],len[N],fa[N],mx[N],mn[N],p,l,ans;
char s[N];
vector<int>v[N];
void insert(int c){
	int p=lst,x=lst=++tot;
	len[x]=len[p]+1;
	while(p&&!ch[p][c]) ch[p][c]=x,p=fa[p];
	if(!p){fa[x]=1;return ;}
	int q=ch[p][c],Q;
	if(len[q]==len[p]+1){fa[x]=q;return ;}
	Q=++tot,memcpy(ch[Q],ch[q],sizeof(ch[q]));
	fa[Q]=fa[q],len[Q]=len[p]+1,fa[q]=fa[x]=Q;
	while(p&&ch[p][c]==q) ch[p][c]=Q,p=fa[p]; 
}
void dfs(int x,int fa){
	for(int y:v[x])
		if(y!=fa) dfs(y,x),mx[x]=max(mx[x],min(mx[y],len[x]));
}
signed main(){
	scanf("%d",&t);
	while(t--){ 
		scanf("%d%s",&k,s+1),n=strlen(s+1),k--;
		for(int i=1;i<=tot;i++)
			fa[i]=len[i]=0,v[i].clear(),fill(ch[i],ch[i]+26,0);
		ans=0,tot=lst=1,memset(mn,0x3f,sizeof(mn));
		for(int i=1;i<=n;i++) insert(s[i]-'a');
		for(int i=2;i<=tot;i++) v[fa[i]].push_back(i);
		for(int i=1;i<=k;i++){ 
			scanf("%s",s+1),n=strlen(s+1),p=1,l=0;
			for(int i=1;i<=n;i++){
				int c=s[i]-'a';
				while(p&&!ch[p][c]) p=fa[p],l=len[p];
				if(ch[p][c]) p=ch[p][c],l++;
				else p=1,l=0;
				mx[p]=max(mx[p],l);
			}
			dfs(1,0);
			for(int i=1;i<=tot;i++) mn[i]=min(mn[i],mx[i]),mx[i]=0;
		} 
		for(int i=1;i<=tot;i++) ans=max(ans,mn[i]);
		printf("%d\n",ans);
	} 
	return 0;
}

3. 字典序相关

字典序第 \(k\) 小子串：本质不同/位置不同。

字典序第 \(k\) 小的子串对应 SAM 中字典序第 \(k\) 小的路径。

如果没有本质不同的条件，建 SAM，在 Parent 树上 DP 求出每个状态表示的字符串的出现次数 \(sz\)。

再在 DAWG 上按照字典序跑，跑到一个节点就令 \(k\gets k-sz_i\)，并转移。没有转移可走时递归回溯。当 \(k=0\) 时，当前跑到的字符串记为所求。

但是没有转移可走时会回溯，某些状态在遍历过一遍后又回溯到上一状态，不能可能作为答案，复杂度爆炸。考虑预处理经过某一状态的路径条数 \(sum\)，转移到某状态前先判断 \(sum\) 是否 \(<k\)，若满足条件，则令 \(k\gets k-sum\)，并直接考虑下一转移。

如果要求本质不同，直接赋 \(sz_i=1\)，即钦定每个子串仅出现 \(1\) 次，再按上述过程跑即可。

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5,M=30;
int n,t,k,x,lst=1,tot=1,ch[N][M],len[N],fa[N],sz[N],f[N],cnt[N],id[N],num;
char s[N],ans[N];
void insert(int c){
	int p=lst,x=lst=++tot;
	sz[x]=1,len[x]=len[p]+1;
	while(p&&!ch[p][c]) ch[p][c]=x,p=fa[p];
	if(!p){fa[x]=1;return ;}
	int q=ch[p][c],Q;
	if(len[q]==len[p]+1){fa[x]=q;return ;}
	Q=++tot,memcpy(ch[Q],ch[q],sizeof(ch[q]));
	fa[Q]=fa[q],len[Q]=len[p]+1,fa[q]=fa[x]=Q;
	while(p&&ch[p][c]==q) ch[p][c]=Q,p=fa[p];
} 
signed main(){
	scanf("%s%d%d",s+1,&t,&k),n=strlen(s+1);
	for(int i=1;i<=n;i++) insert(s[i]-'a');
	for(int i=1;i<=tot;i++) cnt[len[i]]++;
	for(int i=1;i<=tot;i++) cnt[i]+=cnt[i-1];
	for(int i=1;i<=tot;i++) id[cnt[len[i]]--]=i;
	for(int i=tot;i>=1;i--){
		if(t) sz[fa[id[i]]]+=sz[id[i]];
		else sz[id[i]]=1;
	}
	sz[1]=0;
	for(int i=tot;i>=1;i--){
		x=id[i],f[x]=sz[x];
		for(int j=0;j<26;j++) if(ch[x][j]) f[x]+=f[ch[x][j]];
	}
	if(k>f[1]) puts("-1"),exit(0);
	for(int x=1;;){
		if((k-=sz[x])<=0) break;
		for(int i=0;i<26;i++) if(ch[x][i]){ 
			if(k>f[ch[x][i]]) k-=f[ch[x][i]];
			else{putchar('a'+i),x=ch[x][i];break;} 
		} 
	} 
	return 0;
}

字典序最小的循环移位

串 \(S+S\) 包含 \(S\) 的所有循环移位作为子串。

问题转化为在 \(S+S\) 对应的 SAM 上找最小的长度为 \(|S|\) 的路径。从 \(q_0\) 出发，贪心地访问最小的字符即可。

四、广义 SAM

广义 SAM：SAM 的多串版本。即对多个串建立 SAM。

1. 离线做法

将所有串离线插入到 Trie 树中，依据 Trie 树构造广义 SAM。

将所有字符串插入到 Trie 树中。
对 Trie 进行 BFS 遍历，记录下顺序以及每个节点的父亲。
将得到的 BFS 序列按照顺序，把 Trie 树上的每个节点插入到 SAM 中。\(last\) 为它在 Trie 树上的父亲对应的 SAM 上的节点（其中 \(last\) 表示插入字符之前的节点）。也就是每次找到插入节点的父亲作为 \(last\) 往后接即可。

用 BFS 而不是 DFS 是因为 DFS 可能会被卡。

insert 部分和普通 SAM 一样。加上返回值方便记录 \(last\)。

//Luogu P6139
#include<bits/stdc++.h>
using namespace std;
const int N=3e6+5,M=27;
int n,ch[N][M],pos[N],fa[N],len[N],tot=1;
long long ans;
char s[N];
queue<int>q;
struct Trie{ int ch[N][M],fa[N],c[N],tot;}T; 
void insert_(char* s){
	int len=strlen(s+1),p=1;
	for(int i=1;i<=len;i++){
		int k=s[i]-'a';
		if(!T.ch[p][k]) T.ch[p][k]=++T.tot,T.fa[T.tot]=p,T.c[T.tot]=k;
		p=T.ch[p][k];
	}
}
int insert(int c,int lst){	//将 c 接到 lst 后面。返回值为 c 插入到 SAM 中的节点编号 
	int p=lst,x=++tot;
	len[x]=len[p]+1;
	while(p&&!ch[p][c]) ch[p][c]=x,p=fa[p];
	if(!p){fa[x]=1;return x;}
	int q=ch[p][c],Q;
	if(len[q]==len[p]+1){fa[x]=q;return x;}
	Q=++tot,memcpy(ch[Q],ch[q],sizeof(ch[q]));
	fa[Q]=fa[q],len[Q]=len[p]+1,fa[q]=fa[x]=Q;
	while(p&&ch[p][c]==q) ch[p][c]=Q,p=fa[p];
	return x;
} 
signed main(){
	scanf("%d",&n),T.tot=1;
	for(int i=1;i<=n;i++) scanf("%s",s+1),insert_(s);
	for(int i=0;i<26;i++)
		if(T.ch[1][i]) q.push(T.ch[1][i]);	//插入第一层字符
	pos[1]=1;	//Tire 树上的编号为 1 的节点（根节点）在 SAM 上的位置为 1（根节点） 
	while(q.size()){
		int x=q.front();q.pop();
		pos[x]=insert(T.c[x],pos[T.fa[x]]);	//pos[x]: Trie 上节点 x 的前缀字符串（路径 根到 x 所表示的字符串）在 SAM 中的对应节点编号
		for(int i=0;i<26;i++)
			if(T.ch[x][i]) q.push(T.ch[x][i]);
	}
	for(int i=2;i<=tot;i++) ans+=len[i]-len[fa[i]];
	printf("%lld\n",ans);
	return 0;
}

2. 在线做法

不建立 Trie，直接把给出的串插入到广义 SAM 中。insert 部分和普通 SAM 存在差别。

//Luogu P6139
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e6+5,M=27;
int n,m,ch[N][M],pos[N],fa[N],len[N],lst,tot=1,ans;
char s[N];
int insert(int c,int lst){	//返回值为 c 插入到 SAM 中的节点编号
	int p=lst,x=0; 
	if(!ch[p][c]){	//如果这个节点已存在就不需要新建了
		x=++tot,len[x]=len[p]+1;
		while(p&&!ch[p][c]) ch[p][c]=x,p=fa[p];
	} 
	if(!p){fa[x]=1;return x;}	 //1 
	int q=ch[p][c],Q=0;
	if(len[q]==len[p]+1){fa[x]=q;return x?x:q;}	//2
	Q=++tot,memcpy(ch[Q],ch[q],sizeof(ch[q]));
	fa[Q]=fa[q],len[Q]=len[p]+1,fa[q]=fa[x]=Q;
	while(p&&ch[p][c]==q) ch[p][c]=Q,p=fa[p];
	return x?x:Q;	//3
} 
signed main(){
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){ 
		scanf("%s",s+1),m=strlen(s+1),lst=1;
		for(int j=1;j<=m;j++) lst=insert(s[j]-'a',lst);
	}
	for(int i=2;i<=tot;i++) ans+=len[i]-len[fa[i]];
	printf("%lld\n",ans);
	return 0;
}

可以证明最坏复杂度为线性。

码农公寓