LCP和后缀数组

前言

后缀数组（SA）是一种可以用于处理字符串后缀有关性质，包括 LCP 等的思想。一般复杂度用 $\operatorname{O}(n\log n)$ 版本，有 $\operatorname{O}(n)$ 版本但相对复杂，码量大。本文讨论的是严格的 $\operatorname{O}(n\log n)$ 的。

后缀自动机（SAM）则是一种强有力的数据结构，用于解决有关字符串的很多东西。一般复杂度是 $\operatorname{O}(n)$ 的。因为写博客的时间原因 SAM 暂时咕着。暂时只讨论 SA。

本文可能出现的部分词语定义如下：

• 后缀：字符串 $s$ 的后缀，定义为字符串的某个位置到字符串末尾的子串。特别的，称从第 $i$ 个字符为第一个元素的后缀为第 $i$ 个后缀。
• 前缀：基本同后缀，只是定义为从字符串第一个字符到某个位置的子串。
• 后缀的排名：定义第 $i$ 个后缀的排名，为字符串所有后缀按字典序排序后，第 $i$ 个后缀的排名。
• LCP：定义 $\operatorname{LCP}(i,j)$ 为一个字符串排名为 $i$ 的后缀和排名为 $j$ 的后缀的最长公共前缀，有时只最长公共前缀长度，本文也是如此，有的地方指最长公共前缀，有的地方指最长公共前缀长度。
• 字符串的大小关系：两个字符串比较大小，默认是比较字典序谁先谁后。

此外，在后文中，如果没有特殊定义，则 $s$ 表示需要处理的字符串，$n=\left| s\right|$，即 $s$ 的串长，下标从 $1$ 开始编号。

LCP 的性质与引理

根据 LCP 的定义，有这样两个显然的性质：

• $\operatorname{LCP}(i,j)=\operatorname{LCP}(j,i)$
• 记 $len_i$ 表示排名为 $i$ 的后缀的长度，有 $\operatorname{LCP}(i,i)=len_i$。

这样，计算 LCP 时，对于 $i>j$ 的情况，可以转化为 $i<j$ 的情况做。对于 $i=j$ 的情况，直接用 $sa_i$ 算就行。简化了代码实现的复杂程度。

LCP 的一个重要引理如下：

$\forall 1\leqslant i\leqslant k\leqslant j\leqslant n,\operatorname{LCP}(i,j)=\min(\operatorname{LCP}(i,k),\operatorname{LCP}(k,j))$

引理证明

设 $p=\min(\operatorname{LCP}(i,k),\operatorname{LCP}(k,j))$，显然 $p\leqslant\operatorname{LCP}(i,k),p\leqslant\operatorname{LCP}(k,j)$。

假设 $a$ 为 $s$ 的第 $sa_i$ 个后缀，$b$ 为 $s$ 的第 $sa_j$ 个后缀，$c$ 为 $s$ 的第 $sa_k$ 个后缀。

所以 $a,c$ 的前 $p$ 个字符相同，$b,c$ 的前 $p$ 个字符相同。所以 $a,b$ 的前 $p$ 个字符相同。所以有 $\operatorname{LCP}(i,j)\geqslant p$。

不妨考虑反证法，假设存在一个数 $q$，满足 $\operatorname{LCP}(i,j)=q>p$，也就是 $q\geqslant p+1$。此时一定会满足 $a_{[1,q]}=b_{[1,q]}$，也就有 $a_{p+1}=b_{p+1}$。

因为 $p=\min(\operatorname{LCP}(i,k),\operatorname{LCP}(k,j))$，所以一定满足 $a_{p+1}\neq c_{p+1}\lor b_{p+1}\neq c_{p+1}$（$\lor$ 是或者的意思），而且两者一定有一者满足一者不满足。

但是因为 $a_{p+1}=b_{p+1}$，与前文矛盾。因此不存在一个符合题设的 $q$，且一定有 $\operatorname{LCP}(i,j)\leqslant p$，又因为 $\operatorname{LCP}(i,j)\geqslant p$，所以 $\operatorname{LCP}(i,j)=p$。也就是 $\operatorname{LCP}(i,j)=\min(\operatorname{LCP}(i,k),\operatorname{LCP}(k,j))$。

延伸地，还有一个以此为基础的定理：

$\forall 1\leqslant i<j\leqslant n,\operatorname{LCP}(i,j)=\min_{i<k\leqslant j}(\operatorname{LCP}(k,k-1))$

定理证明

将 $[i,j]$ 拆为两个区间：$[i,i+1]$ 和 $[i+2,j]$。

根据引理，有 $\operatorname{LCP}(i,j)=\min(\operatorname{LCP}(i,i+1),\operatorname{LCP}(i+2,j))$。

而对于 $\operatorname{LCP}(i+2,j)$，我们可以递归地继续拆分下去，也就是变成 $[i+2,i+3]$ 和 $[i+4,j]$。以此类推地递归。最后得到：

$\operatorname{LCP}(i,j)=\min(\operatorname{LCP}(i,i+1),\operatorname{LCP}(i+2,i+3),\operatorname{LCP}(i+4,i+5),\cdots,\operatorname{LCP}(j-1,j))$

也就是 $\min_{i<k\leqslant j}(\operatorname{LCP}(k,k-1))$。

后缀数组

变量含义

后缀数组的一些基本变量和数组如下：

• $sa_i$ 表示排名为 $i$ 的后缀是 $s$ 的第几个后缀。
• $rk_i$ 表示 $s$ 的第 $i$ 个后缀的排名。

考虑到 $s$ 的第 $i$ 个后缀的长度为 $n-i+1$。所以我用 string 记录后缀的时候，可以直接通过获得 size 来判断这是第几个后缀，非常方便。

显然有结论：$rk_{sa_i}=sa_{rk_i}=i$。

引理证明：

对于排名为 $i$ 的后缀，它是 $s$ 的第 $sa_i$ 个后缀，第 $sa_i$ 个后缀的排名就是 $rk_{sa_i}$，所以有 $rk_{sa_i}=i$。

同理有 $sa_{rk_i}=i$。

后缀数组最核心的地方就是如何得到这两个数组。以及如何用这两个数组求出一些东西。

求得 sa 和 rk

暴力

最暴力的方法就是将 $s$ 的所有后缀记录下来，按字典序排序，也就是直接 sort。比较任意两个后缀的大小关系是 $\operatorname{O}(n)$ 的，虽然跑不满，但是总的复杂度还是接近 $\operatorname{O}(n^2\log n)$ 的。相当低效。

暴力的代码如下：

string a[max_n]; // 存储后缀
int sa[max_n],rk[max_n];
inline void SA(){
	a[n][1]=s[n];
	for(register int i=n-1;i>=1;--i){ // 记录后缀
		a[i]=a[i+1];
		a[i].push_back(s[i]);
	}
	sort(a+1,a+1+n); // 直接排序
	for(register int i=1;i<=n;++i){
		int j=n-a[i].size()+1;
		sa[i]=j,
		rk[j]=i;
	}
}

当然这个复杂度太拉垮了。

暴力优化

将比较两个字符串大小从暴力改成 Hash+二分公共前缀。复杂度可以转化为 $\operatorname{O}(n\log^2 n)$。不多赘述。

倍增

我们首先按照每个后缀的第一个字符排序。对于每一个后缀，按照第一个字符的字典序可以给它一个临时排名。这个临时排名显然有可能并列。因为不同后缀的第一个字符可能是相同的。

然后把相邻的字符拼在一起，也就是每个后缀的前两位进行排序。考虑到我们已经排过第一位了，而第一位小的第二位不管怎样这个后缀整体都小，也就是这个时候可以直接只把并列的部分拿出来，然后按照第二位排序就行。如果嫌麻烦，也可以直接按照临时排名为排序第一关键字，第二位上的字符为第二关键字。

这时得到了新的临时排名（更新之前的临时排名），此时再把相邻的两个拼在一起，也就是每个后缀的前四位进行排序。考虑到任意连续的两个字符拼在一起的排名已经出来了。这一次排序可以按照前两个字符排名为第一关键字，后两个字符排名为第二关键字。进行排序。

以此类推排序，上一次按照前 $x$ 个字符排序，这一次就按照前 $2x$ 个字符排序。在什么时候结束呢？很显然，如果这一次得到的临时排名没有出现并列，说明这个时候的排名已经是非常严谨的最终排名了。按照这种排序方法显然不会出问题。此时的排名就是最终的 $rk$ 数组。然后根据 $rk_{sa_i}=i$，可以得到 $sa$ 数组。

这样整体的排序，sort 的 $n\log n$ 还在，但是变成了双关键字排序，也就是单次比较大小是 $\operatorname{O}(1)$ 的。因为最坏要排序 $\log n$ 次。因此整体复杂度是 $\operatorname{O}(n\log^2 n)$ 的。

基数排序优化

考虑到我们已经把它转化成双关键字排序排序了，为什么不试试基数排序呢？

我们可以开两个桶，一个装第一关键字，一个装第二关键字。每次我们先依次把每个元素放进第二关键字的桶里面。然后按顺序取出。这时各个元素之间是按照第二关键字排序好的。然后再依次放进第一关键字的桶里面，按顺序取出。这时各个元素之间按照第一关键字排好了，对于第一关键字相同的部分，因为前面已经按照第二关键字排过，所以第一关键字相同时保留了第二关键字的排序。

举个例子，假设我们用两位数代表一个元素，第一关键字是十位，第二关键字是个位，待排序（从小到大）的序列为：

$73,09,22,93,43,55,14,28,65,39,81,20$

在第一次排序，也就是第二关键字排序时，建一个第二关键字（即个位）桶，按照原序加入后：

此时再按顺序提出来，原序列变为：$20,81,22,73,93,43,14,55,65,28,09,39$，不难发现是按照个位小到大排序的，个位相同则为原数组顺序。第二次排序的时候，建一个第一关键字（即十位）桶，按此时顺序加入后：

再依次提取出来，原序列变为：$09,14,20,22,28,39,43,55,65,73,81,93$，已经从小到大排好了。这是因为这是按照十位小到大排序的，十位相同则为前面那个数组顺序，而前面那个数组顺序就是个位小到大顺序。所以整体效果就变成了按照十位小到大排序，十位相同则按照个位小到大排序。也就是正确的排序了。

显然基数排序的复杂度（为了方便我们假设桶大小不大于 $n$）是 $\operatorname{O}(n)$ 的，它是基于若干次桶排序进行的。

而前面倍增的时候，我们碰到的就是双关键字排序这样一个问题，用 sort 是 $n\log n$ 的，现在使用基数排序可以优化成单次排序为 $\operatorname{O}(n)$，因为要进行 $\log n$ 次排序，所以总的复杂度是 $\operatorname{O}(n\log n)$ 的。

代码如下：

struct SA{ // 习惯性封装
	int rk[max_n],sa[max_n],tp[max_n],m;
	SA(){m=300;memset(sa,0,sizeof(sa));} // m 表示桶大小
	
	inline void sort(){ // 基数排序
		memset(sm,0,sizeof(sm)); // sm 是桶
		for(register int i=1;i<=n;++i)
			++sm[rk[i]]; // 按顺序放入桶
		for(register int i=1;i<=m;++i)
			sm[i]+=sm[i-1]; 
			// 因为桶里面下标是临时排名，值是多少个
			// 所以可以直接前缀和快速计算排名关系
		for(register int i=n;i>=1;--i){
			sa[sm[rk[tp[i]]]]=tp[i], // 更新 sa
			--sm[rk[tp[i]]]; // 逐渐初始化桶
		}
	}
	inline void build(int a[]){ // 建 SA，a 数组是原串
		// 方便起见将其转化为 int 类型了
		for(register int i=1;i<=n;++i){
			rk[i]=a[i],
			tp[i]=i; // tp[i] 表示第二关键字排名为 i 的后缀的第一关键字位置
		}
		sort(); // 先按照第一个字符排好序

		int len=1;
		while(1){ // 倍增
			int cnt=0;
			for(register int i=1;i<=len;++i)
				tp[++cnt]=n-len+i; // 重新更新
			for(register int i=1;i<=n;++i)
				if(sa[i]>len)
					tp[++cnt]=sa[i]-len;
			sort(),
			memcpy(tp,rk,sizeof(rk)); // 得到排名
			rk[sa[1]]=cnt=1;
			for(register int i=2;i<=n;++i){ // sa 有序了，可直接生成下次排序关键字
				if(tp[sa[i]]==tp[sa[i-1]] && tp[sa[i]+len]==tp[sa[i-1]+len])
					rk[sa[i]]=cnt;
				else
					rk[sa[i]]=++cnt;
			}
			m=cnt,len<<=1; // 更新桶大小和提取后缀前几个字符
			if(cnt>=n) break; // 说明没有并列，已经排好了
		}
	}
}sa;

实际上还有非常复杂的 $\operatorname{O}(n)$ 做法求 $rk$ 和 $sa$，这里并不讨论。

后缀数组求 LCP

前面在 LCP 的性质里面，也提到过：

记 $len_i$ 表示排名为 $i$ 的后缀的长度，有 $\operatorname{LCP}(i,i)=len_i$。

这时候发现 $len_i$ 不就可以转化为 $n-sa_i+1$ 吗？于是就可以求 $\operatorname{LCP}(i,i)$ 了。关键就是 $i\neq j$ 这种的 $\operatorname{LCP}(i,j)$ 怎么求。

结合 LCP 定理。我们设 $ht_i$（其他博客写的是 $height$，我简写了）表示 $\operatorname{LCP}(i,i-1)$。特别的，$ht_1=0$。

根据 LCP 引理，得到 $\operatorname{LCP}(i,j)=\min_{i<k\leqslant j}(ht_k)$。

那么 $ht$ 数组如何求得呢，显然不能直接枚举（复杂度直接爆炸好吗.jpg），因此我们要考虑两个 $ht$ 之间的关系。不妨定义 $h_i$ 表示 $ht_{rk_i}$。那么显然有 $ht_i=h_{sa_i}$。

现在引进一个非常重要的定理：

$h_i\geqslant h_{i-1}-1$

这个证明就非常魔鬼，这里丢出来一个有证明的博客，有意者可以去那里看看。

这个性质保证了除非 $h_i=h{i-1}-1$，不然它就是不降的，有了这样一个高级的性质，就可以进行 $\operatorname{O}(n)$ 地递推了。

递推部分代码如下：

// a 数组是原串
for(register int i=1,j=0;i<=n;++i){
	if(j) --j; // h[i]>=h[i-1]-1
	int k=sa[rk[i]-1];
	while(a[i+j]==a[j+k])
		++j;
	ht[rk[i]]=j; // h[i]=ht[rk[i]]
}

有这样求可以非常好地求出 LCP 了。如果用 st 之类数据结构维护 $ht$ 数组，就可以做到 $n\log n$ 预处理，$\operatorname{O}(1)$ 查询。（什么，你问我 $n\log n$ 太慢了？你求 sa 和 rk 都是 nlog n 那还管什么常数）

除此之外三个典型的字符串问题，都简单提一下：

• 求可重叠最长重复子串：$ht$ 数组最大值。
• 求不可重叠最长重复子串：二分答案 $x$，对 $ht$ 数组的各个连续元素分组，使得每一组的 $ht$ 最小值不小于 $x$。此时枚举每一组，记录最大长度 $max$，最小长度 $min$。如果有 $sa_max-sa_min\geqslant x$ 则更新答案。
• 本质不同的子串数量：枚举每一个后缀，设后缀长度为 $len$，第 $i$ 个后缀对答案的贡献为 $len-sa_i+1-ht_i$。