基础后缀数据结构简记

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

• 后缀数组
  • 后缀排序
  • height 数组
  • 常见应用
• 后缀自动机
  • 结构
  • 构建
  • 应用
  • 广义后缀自动机
• 后缀树
  • 后缀树
  • 构建

后缀数组

后缀排序

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

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

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

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

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)\) 的 .

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 定理导出 .

断言：

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

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

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

最好类似 AC 自动机，得到一个 fail 树状物，对于等价类 \(u\)，考察其所有后缀，记 \(t\) 为和 \(u\) 不在一个等价类里的的最长后缀，\(v\) 是对应等价类，则连边 \((v,u)\) . 由此定义后缀链接 \(\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)\)（如果字符集较大需要使用 Hash）.
（具体看 OI-Wiki 吧）

详细算法流程：

// 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];}
	}
};

应用

求子串出现次数：也就是要求 endpos 集合的大小，子串也就是每个前缀的所有后缀，也就相当于把每个前缀对应的结点在 parent 树的根链上每个点贡献都加一，DFS 一遍即可 .

求本质不同子串数：每个等价类 \(u\) 对应的子串个数就是 \(\maxl(u)-\maxl(\link(u))\)，全部加起来即可 .

求最长公共子串：考虑对一个字符串建 SAM，另一个字符串在上面跳，每次能转移就转移否则跳 link，对于所有位置取 max 即可 .

后缀 LCP：对于 \(u,v\)，\(\maxl(\operatorname{lca}(u,v))\) 就是 \(u,v\) 对应前缀的最长公共后缀（其实算后缀树的结论）.

作为练习可以做一下弦论那题，很简单的（突然想起来 DAG 第 \(k\) 大路径是 CSP 初赛题）.

广义后缀自动机

相当于对多个字符串的所有子串建立的后缀自动机 .

同样考虑每次加一个字符 \(c\) . 对于每个串分别处理一个 \(lst\) 依次加入，只有一种情况是额外的，也就是 \(lst\) 途径 \(c\) 的转移边存在的情况，设其到达点 \(t\) .

讨论是类似的：

• \(\maxl(t)=\maxl(lst)+1\)，说明根本不用加，最后让 \(lst\gets t\) 即可 .
• \(\maxl(t)\neq\maxl(lst)+1\)，类似地分裂 \(t\) 即可 . 这里新的 \(lst\) 应该是分裂出去的结点 .

那么就完了 . 代码基本是一样的我就不放了 .

后缀树

后缀树的东西我也不是很懂，摆了（

后缀树

问题：求出字符串 \(S\) 所有后缀组成的（压缩）Trie .

这里压缩指压缩一条没有向外的边的链，因为只有 \(O(n)\) 个叶子所以这里的结点数是 \(O(n)\) 的 .

构建

其实也就是说要求所有叶子的虚树，考虑那个单调栈维护右链的构建方法，通过 SA 就天然维护了 .

或者也可以通过 SAM 构建，因为反串的 parent 树就是后缀树 .