基础后缀数据结构简记-526互联

约定 \(n\) 是字符串长度 . \(\lcp(s,t)\) 是 \(s,t\) 的 LCP 的长度 .

后缀数组
后缀自动机
后缀树
- 后缀树
- 构建

后缀数组

后缀排序

问题：将字符串 \(S\) 的所有后缀排序 .

核心思想：倍增考虑，把从每个位置子串拆成两个减半长度的子串的双关键字排序 .

使用基数排序即可 \(\Theta(n\log n)\)，这里 \(n\) 和字符集同阶 .

令 \(sa_i\) 是第 \(i\) 小的后缀的开头位置，\(rk_i\) 是 \(S[i:n]\) 的排名 .

Code

有一些常数优化的技巧可以看 OI-Wiki .

const int m = 1000000;
auto comp = [&](int i, int j, int k){return (y[i] == y[j]) && (y[i+k] == y[j+k]);};
for (int i=1; i<=n; i++) ++buc[x[i] = a[i]];
for (int i=1; i<=m; i++) buc[i] += buc[i-1];
for (int i=n; i>=1; i--) sa[buc[x[i]]--] = i;
for (int k=1; k<=n; k<<=1)
{
	int p = 0;
	for (int i=n-k+1; i<=n; i++) y[++p] = i;
	for (int i=1; i<=n; i++)
		if (sa[i] > k) y[++p] = sa[i] - k;
	memset(buc, 0, sizeof buc);
	for (int i=1; i<=n; i++) ++buc[x[y[i]]];
	for (int i=1; i<=m; i++) buc[i] += buc[i-1];
	for (int i=n; i>=1; i--) sa[buc[x[y[i]]]--] = y[i];
	swap(x, y);
	x[sa[1]] = p = 1;
	for (int i=2; i<=n; i++) x[sa[i]] = comp(sa[i], sa[i-1], k) ? p : ++p;
	if (p >= n) break;
	m = p;
}
for (int i=1; i<=n; i++) rk[sa[i]] = i;

height 数组

问题：求解 \(h_i=\lcp(sa_i,sa_{i-1})\) .

核心思想：\(h_{rk_i}\ge h_{rk_{i-1}}-1\)，从而暴力做就是 \(\Theta(n)\) 的 .

Code

for (int i=1, j=0; i<=n; i++)
{
	if (j) --j;
	while (a[i+j] == a[sa[rk[i]-1]+j]) ++j;
	h[rk[i]] = j;
}

常见应用

LCP：变成区间 height 数组的最小值 .

比大小：求出 LCP 后就好处理了 .

本质不同子串：考虑计数重复子串，仔细考察每次加一个子串肯定新增恰 \(h_i\) 个子串，那么就做好了 .

我也没做啥题，就写这三个吧 .

后缀自动机

结构

我们期望得到一个 DFA，恰接受某个字符串 \(S\) 的每个子串 .

对于一个子串 \(T\subseteq S\)，定义 \(\endpos(T)\) 为 \(S\) 中所有 \(T\) 的结束位置所构成的集合 .

字符串的所有子串可以由 endpos 分为若干个等价类，下面称 \(u,v\) 等价当且仅当 \(\endpos(u)=\endpos(v)\) .

考虑由此构建一个自动机，其每个状态对应一种 endpos，这样的自动机就被称为 \(S\) 的后缀自动机，转移就是表示每次加一个字符的影响，这里转移构成的 DAG 也被称作 DAWG . 最小性可以由 Myhill–Nerode 定理导出 .

断言：

满足 \(|u|\le|v|\) 的子串 \(u,v\) 等价当且仅当 \(u\) 在 \(v\) 中的所有出现都作为 \(v\) 的后缀 .
对于子串 \(u,v\)，当 \(u\) 是 \(v\) 的后缀时 \(\endpos(u)\subseteq\endpos(v)\) 否则 \(\endpos(u)\cap\endpos(v)=\varnothing\) .
对于一个等价类其中包含的子串长度肯定是连续的 .

其实仔细想想都是显然的，这里就不详细说明了 .

关于第三个性质，后令 \(\maxl(u),\minl(u)\) 分别表示一种 endpos \(u\) 对应的最长子串长度和最短子串长度 .

最好类似 AC 自动机，得到一个 fail 树状物，对于等价类 \(u\)，考察其所有后缀，记 \(t\) 为和 \(u\) 不在一个等价类里的的最长后缀，\(v\) 是对应等价类，则连边 \((u,v)\) . 由此定义后缀链接 \(\link(u)=v\) .

令根 \(t_0\) 满足 \(\endpos(t_0)=\{-1,0,\cdots,|S|-1\}\)，则断言 \(\link\) 关系组成一棵树（通常称为 parent 树）.

这是相对显然的，如果你注意到 \(\minl(u)=\maxl(\link(u))+1\) 那么问题就不难了 .

parent 树所得到的树也可以表达 endpos 的包含关系，首先 endpos 的包含肯定组成树，那么只需要说明他们等价即可，问题也就是说明 \(\text{endpos}(v) \subsetneq \text{endpos}(\text{link}(v))\)，根据前面的结论这是显然的 .

从而，后缀自动机的基本结构已经被描摹完成 .

构建

这里采用增量构建，也就是说考虑每次加一个字符 \(c\) 产生的影响（这也表明这个算法是在线的）.

假设加入前表示整个字符串的结点是 \(lst\)，加入后是 \(now\)，核心问题就是确定 \(\link(now)\) . 不断跳 \(lst\) 的 link 指针直到跳没了或者其存在一条走 \(c\) 的转移边 . 记最终得到的点是 \(p\)，转到 \(q\)，考察 \(p\) 这个位置的信息 .

如果跳没了那么肯定是连 \(\link(now)=t_0\) 就完了，否则讨论：

\(\maxl(p)+1=\maxl(q)\)，这时候相当于直接继承原来等价类，连 \(\link(now)=p\) 即可 .
\(\maxl(p)+1\neq\maxl(q)\)，这时加入 \(c\) 会导致原等价类分裂，所以需要把 \(p\) 拆成两份，一份作为原来的等价类，另一份作为 \(\link(now)\) . 此时需要把指向 \(q\) 的结点全部改成指向 \(now\) 的 .

仔细地进行分析即可得到加入 \(n\) 个字符的时间复杂度为 \(\Theta(n)\)，这里假设字符集大小 \(|\Sigma|=\Theta(1)\) .
（具体看 OI-Wiki 吧）

详细算法流程：

Code

注意开二倍空间 .

// len : maxl
struct SAM
{
	int t[N][S], link[N], len[N], lst, cc;
	SAM() : lst(1), cc(1){}
	inline void extend(int c)
	{
		int p = lst, now = lst = ++cc;
		len[now] = len[p] + 1;
		while (p && !t[p][c]){t[p][c] = now; p = link[p];}
		if (!p){link[now] = 1; return ;}
		int q = t[p][c];
		if (len[q] == len[p] + 1){link[now] = q; return ;}
		int k = ++cc;
		memcpy(t[k], t[q], sizeof t[q]);
		len[k] = len[p] + 1; link[k] = link[q]; link[now] = link[q] = k;
		while (p && (t[p][c] == q)){t[p][c] = k; p = link[p];}
	}
};