后缀自动机SAM - 洛谷保存站

# 问题

掏出一个包含且仅包含一个字符串 $S$ 所有字串的自动机。

# 原理

显然，有一种 $n^2$ 级别的构图方法：trie 树上存储所有后缀。

然而，可以考虑增量式地去构造。

# Part 1

首先，把原来 $S$ 中的所有字串全部分类，按照**在原串出现位置（末字符）的集合**来划分。它有一些很好的性质。

- 1.一个集合内的字串是最长的那一个串的连续后缀。

- 2.对于两个状态（指一个非空类），要么不交，要么包含。

证明比较容易，用 1 来证 2 就好。

- 3.一定存在 $\{1\},\{2\},\dots,\{n\}$ 这些集合。

显然，$S$ 的 $n$ 个前缀与它们一一对应。

- 4.最终的自动机上的节点就是它们。

- 5.以包含关系构树（被包含连包含），①父亲集合等于儿子集合的并；②祖孙包含关系，非祖孙不交关系；③父亲最长串等于儿子最短串去掉第一个字符。

事实上，这是反串的**后缀树**。$\{1\},\{2\},\dots,\{n\}$ 这些节点的最长串是 $S$ 的所有前缀。当然这棵树也包含了 $S$ 的所有字串信息。

# Part 2

怎么增量构造呢？新增一个字符 $c$ 会使字串多出 $n$ 个以 $c$ 为结尾的后缀，只要把他们全部更新一遍就好了。

记录 Part 1 的父子关系 `fa` 和自动机的 `go`。注意，`go` 是接着走一步，`fa` 是开头删一个。

### 直接继承 $\{n-1\}$ 的 `go`

首先，$\{n-1\}$ 向 $\{n\}$ 连边，代表继承了原先的后缀。根据节点状态的定义，这些字串原来就只在最后出现了一次，就算多了 $c$，也还是只出现一次的。

### 找出现过的更新 `fa` 和 `go`

然后就是就算加 $c$，原来也出现过的那些串。

考虑一个增量构造的大前提，前面 $n-1$ 已经构造好了。换言之，这些串已经可以通过自动机走到了，只要更新 `fa` 就好。然而更美妙的是，其实只需要更新新加入的 $\{n\}$ 的 `fa`，因为原有的早就已经连好了。

因此，目标就是找出最长的、之前出现过的、结尾是 $c$ 的串的类。直接一手暴力上跳，因为之前 $\{n-1\}$ 位置的 `fa` 是处理好的，如果可以沿着某个 `q=go[p=old fa][c]` 走一步，到达的 $q$ 就是我们要找的了。

然而，还有一个小问题，万一找到的等价类里面还有结尾不是 $c$ 的怎么办？（PS：没有的话直接下一步更新 `fa`）

拆成两半。

由于 Part 1 的性质 1，如果把该类里的串按长度排序，一定有一个分界线，使得前一半是需要的，而后一半不是需要的。把需要的拿成一个新类。

至于这个新类的连边关系，出边一定是和原出边的连接情况相同的。而一部分原入边是为了转移这些需要的、被拆成新类的东西，这些入边需要更改到新点。

这些入边的来源是？**$p$ 往上跳一段连续的 `fa`**，$q$ 是刚刚被拆开的原点，$p$ 是 $\{n-1\}$ 的某个祖先，且 `go[p][c]=q`（其实上面用代码定义了）。

为什么呢？再次回到 Part 1 性质 1，能够转移到这些连续串的，一定也是连续的一坨东西加上了 $c$。这就是 $\{n-1\}$ 的 `fa` 了。

至此，`go` 的新一轮构造就已经完成了。

### 更新拆出来的新类的 `fa`

这就简单了。

$\{n\}$ 的 `fa` 是拆出来的新点或者不需要拆的点 $q$。

如果拆过点，根据 Part 1 性质 5.3 来连边就好。

# 最后

为什么是 $O(n)$ 的？

不造。

# 代码

```cpp
namespace SAM{
	const int N=2e6+10;
	int fa[N],go[N][26],tot=1,nw=1,len[N];
	inline void add(int c){
		int p=nw;
		len[nw=++tot]=len[p]+1;
		for(;p&&!go[p][c];p=fa[p]) go[p][c]=nw;
		if(!p) return fa[nw]=1,void();
		int q=go[p][c];
		if(len[p]+1==len[q]) return fa[nw]=q,void();
		len[++tot]=len[p]+1;
		for(int i=0;i<26;++i) go[tot][i]=go[q][i];
		fa[tot]=fa[q],fa[q]=fa[nw]=tot;
		for(;go[p][c]==q;p=fa[p]) go[p][c]=tot;
	}
}
```

# 广义 SAM

把多个模式串的子串排到一颗 SAM 上。

## 功能

可以分别维护每个模式串的信息，且后缀树性质不变。

## 方法

在原来单串 SAM 的基础上加上特判，判断是否已经存在了当前要加的前缀。如果没有，和之前一样。否则，就直接进入拆分点的那一步，原理和流程和之前一样。注意每次加完一个串就把 `nw=1`。

## 代码

```cpp
namespace GSAM{
	const int N=2e6+10;
	int fa[N],go[N][26],tot=1,nw=1,len[N];
	inline void ins(int c){
		if(go[nw][c]){
			int p=nw,q=go[p][c];
			if(len[p]+1==len[q]) return nw=q,void();
			len[nw=++tot]=len[p]+1;
			for(int i=0;i<26;++i) go[tot][i]=go[q][i];
			fa[tot]=fa[q],fa[q]=tot;
			for(;go[p][c]==q;p=fa[p]) go[p][c]=tot;
			return ;
		}
		int p=nw;
		len[nw=++tot]=len[p]+1;
		for(;p&&!go[p][c];p=fa[p]) go[p][c]=nw;
		if(!p) return fa[nw]=1,void();
		int q=go[p][c];
		if(len[p]+1==len[q]) return fa[nw]=q,void();
		len[++tot]=len[p]+1;
		for(int i=0;i<26;++i) go[tot][i]=go[q][i];
		fa[tot]=fa[q],fa[q]=fa[nw]=tot;
		for(;go[p][c]==q;p=fa[p]) go[p][c]=tot;
	}
}

GSAM::nw=1;
		for(int i=1;i<=n;++i) GSAM::ins(a[i]-'a');
```

正在渲染内容...