后缀自动机

标签：子串 cur 后缀 len st link 自动机 operatorname

定义

字符串 \(s\) 的 SAM 是一个接受 \(s\) 的所有后缀的最小 DFA（确定性有限（状态）自动机）。也就是：

SAM 是一个 DAG。节点为状态，边为转移。
图的源点 \(t_0\) 称初始状态。整张图从 \(t_0\) 开始可以遍历到。
转移标有若干字母，从一个节点出发的所有转移均不同。
存在若干终止状态。从 \(t_0\) 到终止状态形成的转移是 \(s\) 的一个后缀。\(s\) 的每个后缀均能由转移得来。
在所有满足上述条件的自动机中，SAM 的节点数最少。

子串性质

SAM 包含 \(s\) 所有字串的信息。从 \(t_0\) 到任一点形成的转移都是 \(s\) 的子串。\(s\) 的每个子串对应 \(t_0\) 开始的一条路径。

一个状态对应一些字符串的集合，这个集合的每个元素对应这些路径。

构建过程

（建议配合 OI-Wiki 食用）

结束位置 endpos

考虑 \(s\) 的非空子串 \(t\)，记 \(\operatorname{endpos}(t)\) 为 \(s\) 中 \(t\) 的所有结束位置。

对于字符串 abcbc，\(\operatorname{endpos}(bc)=3,5\).

两个子串 \(t_1\) 和 \(t_2\) 的 \(\operatorname{endpos}\) 可能相等。所有的非空子串可划分为若干等价类。

SAM 的每个状态对应若干个 \(\operatorname{endpos}\) 相同的子串。
SAM 的状态数等于所有子串的等价类个数及初始状态。

不考虑 SAM 最小性的证明。

一些结论：

\(1.\) 字符串 \(s\) 的两个非空子串 \(u\) 和 \(w\)（不妨设 |u|\le |w|）的 \(\operatorname{endpos}\) 相同，当且仅当 \(u\) 在 \(s\) 中的每次出现都以 \(w\) 后缀的形式存在。
\(2.\) 上述的 \(u\) 和 \(w\)，若 \(u\) 是 \(w\) 的后缀，则 \(\operatorname{endpos}(w)\subseteq\operatorname{endpos}(u)\)，否则 \(\operatorname{endpos}(w)\cap\operatorname{endpos}(u)=\varnothing\).
\(3.\) 同一等价类得任意两子串，短者为长者的后缀，这一些子串长度覆盖一段完整的区间。

后缀链接 link

对于非 \(t_0\) 的状态 \(v\)，其对应具有相同 \(\operatorname{endpos}\) 的等价类。令 \(w\) 为其中最长者，那么其他的都是 \(w\) 的后缀。

将这些后缀按长度降序排序，那么会有前几个包含与这个等价类，其他后缀（包含 \(\varnothing\)）在其他等价类中。令 \(t\) 为后者的最长者，且 \(\operatorname{link}(v)\leftarrow t\).

即 \(\operatorname{link}(v)\) 对应 \(w\) 的最长后缀的另一个 \(\operatorname{endpos}\) 等价类状态。

记 \(t_0\) 对应的只包含它自己的等价类为 \(\operatorname{endpos}(t_0)=\{1,0,\dots,|S|-1\}\).

\(4.\) 所有后缀链接构成以 \(t_0\) 为根的树。

\(\operatorname{link}\) 指向的状态对应严格更短的字符串。

\(5.\) 通过 \(\operatorname{endpos}\) 集合构造的树（子节点集合 \(\subseteq\) 父节点集合）与通过 \(\operatorname{link}\) 构造的树相同。

构建

SAM 可以在线性时间内构建。

从左到右扫描原串，不断在 SAM 上添加新状态。

维护指针 \(last\) 表示当前字符对应的状态。一开始指向初始状态。

读入字符 \(c\)，创建新状态 \(cur\)，令 \(\operatorname{len}(cur)\leftarrow\operatorname{last}+1\)，表示以 \(c\) 结尾的最长子串比 \(last\) 表示的最长子串多了一个字符。
从 \(last\) 开始沿着后缀链接往上跳，找到状态 \(p\) 满足 \(p\) 有一条字符为 \(c\) 的转移边或 \(p=t_0\)。若 \(p\) 满足前一个条件，记这条边指向的状态为 \(q\)，判断 \(\operatorname{len}(p)+1=\operatorname{len}(q)\) 是否成立。
相等则 \(q\) 是 \(cur\) 的后缀链接，令 \(\operatorname{link}(cur)\leftarrow q\)，在 \(p\) 和 \(cur\) 之间添加字符为 \(c\) 的转移边。
不相等则 \(q\) 表示多个不同长度的子串，将 \(q\) 复制出一个新状态 \(tp\)，令 \(\operatorname{len}(tp)\leftarrow\operatorname{len}(p)+1\)，表示 \(tp\) 仅表示长为 \(\operatorname{len}(p)+1\) 的子串。令 \(p\) 指向 \(q\) 的转移重新指向 \(tp\)，令 \(\operatorname{link}(q),\operatorname{link}(cur)\leftarrow tp\).
在 \(p\) 和 \(cur\) 之间添加字符为 \(c\) 的转移边。另外地，若 \(p=t_0\)，令 \(\operatorname{link}(cur)\leftarrow p\).
令 \(last\leftarrow cur\)，继续扫串。

假设字符集大小 \(|\Sigma|\) 为常数，则构建复杂度线性，否则渐进复杂度
\(O(n\log|\Sigma|)\).

代码实现

空间是 \(O(n|\Sigma|)\) 的。

struct state{
	int len,link,siz;
	map<char,int>next;
}st[N];
int node,last;
void SAM_init(){
	st[0].len=0,st[0].link=-1;
	node++,last=0;
}
void SAM_extend(char c){
	int cur=node++;
	st[cur].len=st[last].len+1,st[cur].siz=1;
	int p=last;
	while(p!=-1&&!st[p].next.count(c)){
		st[p].next[c]=cur;
		p=st[p].link;
	}
	if(p==-1)st[cur].link=0;
	else{
		int q=st[p].next[c];
		if(st[p].len+1==st[q].len)
			st[cur].link=q;
		else{
			int tp=node++;
			st[tp].len=st[p].len+1;
			st[tp].next=st[q].next;
			st[tp].link=st[q].link;
			while(p!=-1&&st[p].next[c]==q){
				st[p].next[c]=tp;
				p=st[p].link;
			}
			st[q].link=st[cur].link=tp;
		}
	}
	last=cur;
}