后缀数组

后缀数组利用倍增思想

求出sa rank数组

然后利用这两个数组求height

最后利用height 解决一些问题

所以啥是sa rank height啊？

---

算法流程

定义

1.后缀数组sa

将按字典序排序后的后缀的开头位置顺次放入了sa中

换个说法就是

sa[i]表示字典序排名为i的后缀的开头的下标

2.名次数组rank

rank[i]表示以i为开头的后缀的排名

简单点说

sa[i]表示排第i的是谁

rank[i]表示i排第几

他们两个互为反函数（又是数学）

3.height数组

height[i]表示sa[i]与sa[i-1]这两个（下标所代表的）后缀的最长公共前缀的长度

height数组有一些性质 一会再说

---

计数排序&&基数排序

在求sa之前 我们需要知道一下计数排序和基数排序

计数排序

它的工作过程分为三个步骤：

1. 计算每个数出现了几次；
2. 求出每个数出现次数的 前缀和
3. 利用出现次数的前缀和，从右至左计算每个数的排名。

计数排序代码

const int N = 100010;
const int W = 100010;

int n, w, a[N], cnt[W], b[N];

void counting_sort() {
  memset(cnt, 0, sizeof(cnt));
  for (int i = 1; i <= n; ++i) ++cnt[a[i]];
  for (int i = 1; i <= w; ++i) cnt[i] += cnt[i - 1];
  for (int i = n; i >= 1; --i) b[cnt[a[i]]--] = a[i];
}

基数排序

基数排序（英语：Radix sort）是一种非比较型的排序算法，最早用于解决卡片排序的问题。

基数排序将待排序的元素拆分为k个关键字，逐一对各个关键字排序后完成对所有元素的排序。

如果关键字值域不大 就可以将计数排序作为基数排序的内核

后缀数组就是利用了以计数排序为内核的基数排序（像绕口令）

---

倍增求后缀数组

利用前$2^{k-1}$（第一关键字） 和后$2^{k-1}$（第二关键字）的rank值求当前$2^k$的rank

详见代码

来源 @

时间复杂度O(n log n)

int n;
int sa[N<<1],x[N<<1],y[N<<1],cnt[N];
string s;
void GetSa()
{
	int m=128;//计数排序的值域
	memset(cnt, 0, sizeof cnt);//对原串字符计数排序，获取各字符排名
	for (int i = 1; i <= n; i++) cnt[x[i]=s[i-1]]++;//统计个数
	for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];//前缀和
	for (int i = n; i; i--) sa[cnt[x[i]]--] = i;
        //第一次计数排序结束 排完了长度为1的

	for(int k=1;k<=n;k<<=1)//倍增求SA，k为当前处理串长
	{

		int p=0;//根据上一轮求得的sa数组计算下一轮 根据第二关键字排序的顺序
		for(int i=n;i>n-k;i--) y[++p]=i;//第二关键字排序其实就是把超出串范围（即 sa[i]+w>n）的 sa[i] 放到 sa 数组头部
		for(int i=1;i<=n;i++) if(sa[i]>k) y[++p]=sa[i]-k;//然后把剩下的依原顺序放入

		memset(cnt,0,sizeof cnt);//对第一关键字进行计数排序
		for(int i=1;i<=n;i++) cnt[x[y[i]]]++;
		for(int i=1;i<=m;i++) cnt[i]+=cnt[i-1];
		for(int i=n;i;i--) sa[cnt[x[y[i]]]--]=y[i];

		swap(x,y);m=0;//将 y 赋为 x 并重新计算 x（临时排名）
		for(int i=1;i<=n;i++)
			if(y[sa[i]]==y[sa[i-1]] && y[sa[i]+k]==y[sa[i-1]+k]) x[sa[i]]=m;
			else x[sa[i]]=++m;
		if(m==n) break;//如果已经得出m个排名即为排序完毕直接结束
	}
}

---

求height数组

前面说到height数组有特殊性质 现在就说（我没忘）

---

1.对于任意前缀 j k 满足 rank[j]<rank[k]

j k 的最长公共前缀为$min_{rank[j]<i<=rank[k]} height[i]$

简单证明：

若i k j 相邻 显而易见

$LCP(i,j)=min(LCP(i,k),LCP(k,j))$

不相邻同理

2.令h[i]=height[rank[i]]

h[i]>=h[i-1]-1

这个性质保证了在O(n)的时间复杂度内求height数组

求height代码如下

void gethei()
{
	for(int i=1;i<=n;i++) rk[sa[i]]=i;//根据sa求rk数组
	for(int i=1,h=0;i<=n;hei[rk[i++]]=h)//h为前缀长度，遍历每个后缀，循环结束后h即为height
 		for(h?h--:0;s[i+h]==s[sa[rk[i]-1]+h];h++);//hei最小为上一个hei-1,然后扩展
}

到此就结束了后缀数组的过程 求出了做题用的height数组

终于写完了后缀数组 好难 撒花