后缀数组小计

0 前言

被迫上班了属于是

前置知识

• 倍增
• 基数排序

基数排序

这个很好理解
举个例子 : 对 \(n\) 对二元组 \((x,y)\) 排序 优先比较关键字 \(x\) 相同再比较关键字 \(y\)
第一步：以 \(y\) 为基准 从小到大把所有二元组排序 得到 \(y\) 递增的序列
第二部：以 \(x\) 为基准 从小到大把所有二元组排序 得到 \(x\) 递增的序列
因为保证原数列顺序不变 在 \(x\) 递增的同时 \(y\) 也是递增的 排序完毕
令值域为 \(w\) 时间复杂度为 \(O(w)\)
举个例子：
原 : \((3,4)\space (3,1)\space (1,5)\space (2,4)\)
第一次排序 : \((3,1)\space (3,4)\space (2,4)\space (1,5)\)
第二次排序 : \((1,5)\space (2,4)\space (3,1)\space (3,4)\)
听起来很简单 但是代码可不简单

void Qsort() {
	rep(i, 1, m) a[i] = 0;
	rep(i, 1, n) ++ a[rk[i]];
	rep(i, 1, m) a[i] += a[i - 1];
	drep(i, 1, n) sa[a[rk[tp[i]]] --] = tp[i];
}

来分析一下目前最同用的伪代码

1 基本概念

我们规定如下的数组：

• \(rk[i]\) 表示开头下标为 \(i\) 的后缀的排名
• \(sa[i]\) 即常说的后缀数组 表示排名为 \(i\) 的后缀开头下标

显然 有性质 \(sa[rk[i]]=rk[sa[i]]=i\)
理解一下：
对于 \(sa[rk[i]]=i\) 表示取出第 \(i\) 个后缀的排名 再引用该排名的位置即 \(i\)
对于 \(rk[sa[i]]=i\) 表示取出排名为 \(i\) 的后缀的位置 再求出该位置的排名即 \(i\)

(OI wiki 的图)

2 后缀数组求法

不难发现 只需要求出 \(rk\) 数组 \(sa\) 数组自然就能求出

1.\(O(n^2\log n)\)

这个肯定自己想都能想出来
先 \(O(n)\) 枚举所有后缀 然后使用快排
因为字符串比较时间是 \(O(n)\) 的 因此总的时间复杂度是\(O(n\times n\log n)\) 即 \(O(n^2\log n)\)

2.\(O(n\log^2 n)\)

我们发现时间瓶颈 \(n\) 卡在了 \(O(n)\) 的比较上
我们想想怎么优化排序 于是倍增法就出来了
主要思想就是一部分 一部分粘合

(OI wiki)

这一部分很好理解
以 最长的后缀 (下标从 \(1\) 开始为例)

首先 得到单个字母的 \(rank\) 值 (第一步)
然后 求出子串 \([1\to 2]\) 当前的 \(rank\)
怎么求？很好理解 记录第一关键字 \(x=rk1\) 第二关键字 \(y=rk2\)
排序所有的 \((x,y)\) 二元组可以得到所有当前的后缀排名
这时 会发现最后一位已经无法向后拓展了 (即第二次排序时最后的第二关键字)
那么 这时 记这位为 \(0\)
思考一下 这样 就与字符串比较的规则相符了

然后 同理 第三次求出子串 \([1\to 4]\)
第四次求出子串 \([1\to 8]\)

这样 不难发现 当所有的数第二关键字为 \(0\) 时 此时便得到了所有后缀
此时 第一关键字便是 \(sa\) 数组
非常巧妙的方法 这样 将比较是时间复杂度缩短为常数级别

现在分析时间复杂度
不难发现 倍增的次数为 \(O(\log n)\)
每次使用快排 时间复杂度 \(O(n\log n)\)

总体时间复杂度 \(O(n\log^2 n)\)

别看理论简单 代码却很抽象

#include<bits/stdc++.h>
#define N 1000005
using namespace std;
char s[N]; 
int n;
int sa[N],rk[N*2],lrk[N*2];
int k;
bool cmp(int a,int b)
{
	return rk[a]^rk[b]?rk[a]<rk[b]:rk[a+k]<rk[b+k];//先以第一关键字排序 再以第二关键字排序 
}
int main()
{
	scanf("%s",s+1);
	n=strlen(s+1);
	for(int i=1;i<=n;i++) sa[i]=i,rk[i]=s[i];//初始化 将第一次排名处理好  存入未排序的sa数组 
	for(k=1;k<n;k<<=1)
	{
		sort(sa+1,sa+1+n,cmp);//算出当前子串数组的sa 下面的步骤就是用sa推rk 
		memcpy(lrk,rk,sizeof rk);//复制一份rk数组 
		int p=0;
		for(int i=1;i<=n;i++)
			if(lrk[sa[i]]==lrk[sa[i-1]]&&lrk[sa[i]+k]==lrk[sa[i-1]+k])
				rk[sa[i]]=p;//枚举排名 i 比较与上一个拼接是否相同 相同就不是增大的排名 
			else rk[sa[i]]=++p;
	}
	for(int i=1;i<=n;i++) printf("%d ",sa[i]);
	return 0;
}

注意几个细节 \(k\) 是全局变量 否则无法参加 cmp 函数的计算
理解难点在于用 \(sa\) 推 \(rk\)
以求 \(rk_2\) 为例

• step \(1\) 通过 \(sa\) 数组取出在新 \(rk\) 中排名为 \(1\space 2\) 的位置
• step \(2\) 比较在旧 \(rk\) 中排名为 \(1\space 2\) 时的拼接是否相同
• step \(3\) 如果有效 在新 \(rk\) 中 排名为 \(1\space 2\) 位置的值

3.\(O(n\log n)\)

非常简单的优化
容易发现 瓶颈在于快排
发现有 \(x,y\le n\) 的性质
双关键字排序将快排换为基数排序即可

理论结束 建议两种代码都写一次