标签：LCP 后缀笔记数组 sa 排序 operatorname rk

\(\text{后缀数组学习笔记}\)

一、定义

对于下标从 \(1\) 开始，长度为 \(n\) 的字符串 \(s\)，我们定义后缀 \(i\) 表示字符串 \(s[i, n]\)。

对于后缀数组，我们定义 \(sa(i)\) 表示所有后缀按字典序排序后第 \(i\) 小的后缀的编号。

例如对于字符串 aabaaab，它有 \(7\) 个后缀，下边我们列出排序后的结果：

aaab
aab
aabaaab
ab
abaaab
b
baaab

那么容易得到 \(sa(1)=4,sa(2)=5,\cdots\)。和常见求排名的数据结构一样，同样需要定义一个 \(rk(i)\) 表示每个后缀的排名。例如 \(rk(4)=1,rk(5)=2,\cdots\)。

容易发现的是 sa[rk[i]] = rk[sa[i]] = i。

二、后缀数组的求解

1. 暴力

直接预处理出 \(s\) 的 \(n\) 个后缀再排序。排序的复杂度是 \(O(n\log n)\)，字符串的比较是 \(O(n)\)，于是总的复杂度是 \(O(n^2\log n)\)。

2. 倍增

(1) 倍增求解后缀数组

考虑我们比较两个字符串大小的过程。考察对于两个长度为 \(2n\) 的字符串 \(s,t\)，\(s>t\) 时的条件：

\(s[1,n]>t[1,n]\)
或是 \(s[1,n]=t[1,n]\) 且 \(s[n+1,2n]>t[n+1,2n]\)。

那么我们将长度为 \(n\) 的字符串拆成了两个长度为 \(\dfrac{n}{2}\) 的字符串来比较。这样将大问题减半拆解的做法显然可以倍增解决。

于是让我们描述这个做法的过程：

首先对每个字符排序，得到 \(sa_1,rk_1\)。
套用上面的过程，用 \(rk_1(i),rk_1(i+1)\) 作为第一、二关键字排序，得到长度为 \(2\) 的子串的排名。
每次都这样做，用长度为 \(\dfrac{w}{2}\) 的子串的排名得到长度为 \(w\) 的子串的排名。
考虑这样做的疏漏：对于 \(rk_{\frac{w}{2}}(i+\frac{w}{2})\)，这个下标存在 \(>n\) 的情形，此时视为 \(0\) 即可。对于长度 \(<w\) 的后缀，并不存在子串 \(s[i,i+w-1]\)，此时将子串视为 \(s[i,n]\)。
当 \(w\ge n\) 时，此时的 \(sa_w,rk_w\) 就是所求。

对于复杂度的分析，倍增是 \(O(\log n)\) 的，排序是 \(O(n\log n)\) 的，于是复杂度是 \(O(n\log^2 n)\)。

(2) 基数排序优化

考虑复杂度的可优化部分：倍增是难以优化的，但是对于排序，我们可以浅浅利用一番其性质。注意到每次排序的是一个二元组，于是考虑进行基数排序优化。那么让我们插播一下基数排序的内容。

基数排序是建立在桶排序的基础之上的。本质上是一个根据优先级逐层确定顺序的过程。对于一些正整数的排序过程是这样的：

先按照个位的不同排序，放入桶中；
再按照十位的不同排序，但要注意放入桶中的顺序是个位排序后的顺序；
依次排完所有十进制位。

对于这样做的正确性，事实上体现着基数排序的核心就是多关键字的排序。对于复杂度分析，令 \(V\) 表示值域，\(m\) 表示关键字的个数，那么桶排序是复杂度是 \(O(n+V)\)，那么总的复杂度就是 \(O(mn+mV)\)。

那么对于后缀数组的排序，\(m=2,a\le n\)，那么总的复杂度就是 \(O(n)\) 的。这样一来，总的复杂度就是 \(O(n\log n)\)。

(3) 一些常数优化

第二关键字无需桶排序。原因是对于 \(i\in[n-w+1,n]\)，它们的值一定是 \(0\)，一定最小，直接扔到数组最前面即可。对于剩下的后缀，有 \(sa(i)>w\)，于是放入和它拼接而成的 \(sa(i)-w\) 即可。
每次基数排序的值域设为 \(rk\) 的值域即可。
若 \(rk\) 的值域已经为 \(n\)，显然可以直接跳出。

代码：

void SA(int M) {
	int m = M, p = 0;
	for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
	for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
	for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
	for (int w = 1;; w <<= 1, m = p) {
		int cur = 0;
		for (int i = n - w + 1; i <= n; i++) id[++cur] = i;
		for (int i = 1; i <= n; i++)
			if (sa[i] > w) id[++cur] = sa[i] - w;
		for (int i = 1; i <= m; i++) cnt[i] = 0;
		for (int i = 1; i <= n; i++) cnt[rk[i]]++;
		for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for (int i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i];
		swap(lk, rk);
		p = 0;
		for (int i = 1; i <= n; i++) {
			if (lk[sa[i]] == lk[sa[i - 1]] && lk[sa[i] + w] == lk[sa[i - 1] + w]) rk[sa[i]] = p;
			else rk[sa[i]] = ++p;
		}
		if (p == n) break;
	}
}

其中 M 是初始的值域范围，由题意得到。

然而只会求后缀数组并没有什么用处，我们还需要知道一些奇妙的性质。

三、\(\operatorname{LCP}\) 的一些性质

性质 \(1\)

\[\operatorname{LCP}(sa(i),sa(k))=\min(\operatorname{LCP}sa(i),sa(j)),\operatorname{LCP}(sa(j),sa(k)))(i<j<k) \]

我们记 \(p=\min(\operatorname{LCP}(sa(i),sa(j)),\operatorname{LCP}(sa(j),sa(k)))\)。那么 \(sa(i)\) 和 \(sa(k)\) 的前 \(p\) 位是相等的。于是 \(\operatorname{LCP}(sa(i),sa(k))\ge p\)。

对于 \(sa(i)\) 和 \(sa(k)\) 的第 \(p+1\) 位，我们记 \(sa(i),sa(j),sa(k)\) 的第 \(p+1\) 位为 \(w(i),w(j),w(k)\)，分类讨论：

\(\operatorname{LCP}(sa(i),sa(j))=\operatorname{LCP}(sa(j),sa(k))=p\)，此时显然第 \(p+1\) 位的 \(sa(i),sa(j)\) 不同，且 \(w(i)<w(j)<w(k)\)。
\(\operatorname{LCP}(sa(i),sa(j))>\operatorname{LCP}(sa(j),sa(k))=p\)，此时 \(w(i)=w(j)<w(k)\)。
\(\operatorname{LCP}(sa(j),sa(k))>\operatorname{LCP}(sa(i),sa(j))=p\)，此时 \(w(i)<w(j)=w(k)\)。

也就是无论如何，\(w(i)<w(k)\)，于是 \(\operatorname{LCP}(sa(i),sa(j))\le p\)，于是 \(\operatorname{LCP}(sa(i),sa(j))=p\)。

性质 \(2\)

\[\operatorname{LCP}(sa(i),sa(j))=\min_{k=i+1}^{j}\operatorname{LCP}(sa(k-1),sa(k)) \]

这样一条性质由性质 \(1\) 是容易通过数学归纳法得到的。

性质 \(3\)

\[\operatorname{LCP}(sa(j),sa(k))\ge\operatorname{LCP}(sa(i),sa(k))(i\le j\le k) \]

这个性质可以通过 \(\min\) 的不升性结合性质 \(2\) 得到。

四、\(\operatorname{Height}\) 数组

1. 定义

我们定义 \(\operatorname{LCP}(i,j)\) 表示 \(s\) 中两个后缀 \(i,j\) 的最长公共前缀。

定义 \(\operatorname{Height}(i)=\operatorname{LCP}(sa(i),sa(i-1))\)，规定 \(\operatorname{Height}(1)=0\)。以下为了方便，用 \(h\) 代指 \(\operatorname{Height}\) 数组。

2. 求法

引理：\(h(rk(i))\ge h(rk(i-1))-1\)。

考虑证明。若 \(h(rk(i-1))\le 1\)，原式显然成立，否则有 \(h(rk(i-1))>1\)，那么考虑后缀 \(i,j\)，其中有 \(rk(j)+1=rk(i)\)，那么当两个后缀的首字母相同时，显然删掉这个首字母两个新的后缀 \(j+1,i+1\) 的排名的先后顺序是不变的，有 \(rk(j+1)<rk(i+1)\)，那么有 \(rk(j+1)\le rk(i+1)-1\)。结合性质 \(3\) 可推出

\[h(rk(i+1))=\operatorname{LCP}(sa(rk(i+1)),sa(rk(i+1)-1))\ge \operatorname{LCP}(sa(rk(i+1)),sa(rk(j+1)))=\operatorname{LCP}(i+1,j+1) \]

根据定义 \(h(rk(i))=\operatorname{LCP}(sa(rk(i)),sa(rk(i)-1))=\operatorname{LCP}(i,j)=\operatorname{LCP}(i+1,j+1)+1\)，那么移项后得到 \(h(rk(i+1))\ge h(rk(i))-1\)，证毕。

标签：LCP,后缀,笔记,数组,sa,排序,operatorname,rk
From： https://www.cnblogs.com/Rock-N-Roll/p/18648804

后缀数组学习笔记