后缀自动机瞎扯-拓冰建站

后缀自动机实际上就是接收字符串所有后缀的最小 DFA，它的一个基本性质就是任何一个子串都能表示为从根节点出发的一条路径。它的点数和边数都只有 \(O(n)\) 级别，所以它能在更好的复杂度内解决一些子串的出现次数之类的问题。由于我太菜了，这里只会说 SAM 的构造。

约定： 若无特殊说明，假设 \(s\) 为文本串，\(rt\) 为 SAM 的根节点。

一、基本定义

定义 1： 定义一个字符串 \(t\) 的 \(\text{endpos}\) 为一个集合，该集合的元素为 \(t\) 在 \(s\) 的出现位置的末尾的下标。比如，\(s=\)ababab，\(t=\)ba，则 \(\text{endpos}=\{3,5\}\)。

定义 2： 定义一个等价类为一个字符串集合，该集合中的元素的 \(\text{endpos}\) 相同。

根据定义我们可以得到一些简单的性质：

引理 1： 设 \(s,t\) 分别为字符串，且 \(|s|\le |t|\)。若 \(\text{endpos}(s)=\text{endpos}(t)\)，则 \(s\) 为 \(t\) 的后缀。

引理 2： 设 \(s,t\) 分别为字符串，若 \(\text{endpos}(t)\subseteq\text{endpos}(s)\)，则 \(s\) 为 \(t\) 的后缀反过来也是成立的。

定义 3： 定义等价类 \(S\) 的 \(\text{len}(S)\) 为包含在 \(S\) 内的字符串的最大长度。

引理 3： 在等价类 \(S\) 内的所有字符串的长度形成一段连续区间。证明可以考虑反证，也可以感性理解。

二、为构建 SAM 做准备

定义 4： 定义等价类 \(S\) 的 \(\text{link}(S)\) 为 \(S\) 内串长最短的字符串去掉最前面的字符后的字符串所属的等价类。

由此我们可以得到一个比较重要的性质：等价类 \(S\) 内包含的字符串数量为 \(\text{len}(S)-\text{len}(\text{link}(S))\)。这对于求一些什么本质不同子串数量、本质不同子串总长啥的有重要作用。

并且根据定义 4 不难发现，如果在 \((i,\text{link}(i))\) 间建一条边，那么最终会形成一棵树。这棵树通常被称为 parent 树。并且等价类 \(S\) 在该树上的所有祖先所包含的字符串都是 \(S\) 内字符串的后缀。

定义 5： 定义 \(nxt(i,c)\) 表示在等价类 \(i\) 后面加上字符 \(c\) 之后转移到的等价类。

引理 4： 若 \(nxt(i,c)\) 存在，则 \(nxt(i,c)\) 唯一。证明也可以考虑反证。

虽然比较突兀，但这两个结论对于复杂度证明确实很重要：

性质： SAM 的点数 \(\le 2n-1\)，边数 \(\le 3n-4\)。

三、构建 SAM

SAM 构建算法是一个在线算法，它支持动态的插入一个字符。

现在考虑一个字符串 \(s[1:n]\)，现在我要往字符串后面添加字符 \(c\)。显而易见的，\(s[1:n]+c\) 将成为一个新的等价类，设该等价类的编号为 \(cur\)，令 \(x\) 为之前的 \(cur\)，即 \(s[1:n]\) 所属的等价类。那么显然有 \(\text{len}(cur)=\text{len}(x)+1\)。

考虑求 \(\text{link}(cur)\)，也就是找到 \(s[1:n]\) 长度最大的后缀 \(p\) 使得 \(s[p:n]+c\) 在 \(s[1:n]\) 出现过。根据引理 2，我们只需要枚举 \(x\) 的祖先就能找到合法的 \(p\) 了：如果 \(nxt(p,c)\) 存在，那么这个 \(p\) 就是合法的；否则，令 \(nxt(p,c)=cur\)，然后 \(p=\text{link}(p)\)。如果不存在这样的 \(p\)，那么 \(\text{link}(cur)=rt\)，之后就没有它什么事了，否则 \(\text{link}(cur)\) 就初步确定为 \(nxt(p,c)\)，设 \(y=nxt(p,c)\)。

不难发现，此时比 \(p\) 更长的那些后缀加上 \(c\) 和 \(y\) 不再属于一个等价类。那么，如果 \(s[p:n]+c\) 是 \(y\) 内的最长字符串，那么 \(\text{link}(cur)\) 最终确定为 \(y\)；否则，此时一定存在一个比 \(p\) 更长的后缀加上 \(c\) 在 \(y\) 里面，现在我们要把它们分裂，\(s[p:n]+c\) 及比它更短的字符串是一个等价类，设为 \(up\)；比 \(s[p:n]+c\) 更长的字符串是另一个等价类，设为 \(dn\)。

现在我们要完成以下操作：

将原 \(\text{link}(*)=y\) 的所有 \(\text{link}\) 全部改为 \(dn\)。
将原 \(nxt(*,c)=y\) 的所有 \(nxt\) 全部改为 \(up\) 或 \(dn\)。
更新 \(up,dn\) 的 \(\text{len},\text{link},nxt\) 等信息。

为了减少空间浪费和修改方便的需要，我们可以让 \(up,dn\) 中的一个继承 \(y\) 这个编号，这样只需要新建一个节点即可。这里让 \(dn\) 继承 \(y\) 的编号最好，新建 \(up=z\)，此时操作 1 可以直接无视，而 \(\text{link}(y)=\text{link}(cur)=z\)，\(\text{link}(z)\) 继承先前的 \(\text{link}(y)\)。对于操作 2，有结论：\(nxt(*,c)=y\) 在 \(p\) 的祖先链上形成一段前缀，暴力修改即可。

可以证明：上述复杂度是 \(O(n)\)。~~我有一种很简单的证明，但是我忘了。~~

代码：

int nxt[maxn<<1][26],lin[maxn<<1],len[maxn<<1];
int cur,tot;
void ins(int ch){int x=cur;cur=++tot,len[cur]=len[x]+1;while(x!=-1&&!nxt[x][ch])nxt[x][ch]=cur,x=lin[x];if(x==-1)return lin[cur]=0,void();int y=nxt[x][ch];if(len[y]==len[x]+1)return lin[cur]=y,void();int z=++tot;memcpy(nxt[z],nxt[y],sizeof nxt[y]);lin[z]=lin[y],len[z]=len[x]+1,lin[y]=lin[cur]=z;while(x!=-1&&nxt[x][ch]==y)nxt[x][ch]=z,x=lin[x];
}