后缀数组SA

$rank[i]$:后缀i~n的排名

$sa[i]$：排名为i的后缀的起始下标

$h[i]$:起始下标为i的后缀和比它前一名的后缀的最长公共前缀

$height[i]$ 排名为i的后缀和比它前一名的后缀的最长公共前缀

求sa数组

$Olog(n)$

代码：


#include<bits/stdc++.h>
using namespace std;
const int N=1000010;
int rr[N],rr2[N],sa[N];//rr[N]:第二关键字，rr[rr2[N]]第一关键字 
int c[N];//桶 
int cnt,n,m; 
string a;
int main()
{
	cin>>a;
	m='z';//m代表不同排名的个数，即桶的范围 
	n=a.size();
	for(int i=1;i<=n;i++)rr[i]=a[i-1];
	for(int i=1;i<=n;i++)c[rr[i]]++;//插入桶 
	for(int i=1;i<=m;i++)c[i]+=c[i-1];
	for(int i=n;i>=1;i--)sa[c[rr[i]]--]=i;//倒序枚举！！！ 
	for(int k=1;k<=n;k<<=1){ 
		memset(c,0,sizeof c);//不能漏 
		cnt=0;
		//第一次相当于将每个值对应的(a,b)中的b排序 ，第二次则以a来 
		for(int i=n-k+1;i<=n;i++)rr2[++cnt]=i;//不存在第二关键字，相当于b=0，在第一次排序中应该排到最前面 
		for(int i=1;i<=n;i++)if(sa[i]>k)rr2[++cnt]=sa[i]-k;//改为第一关键字 
		for(int i=1;i<=n;i++)c[rr[i]]++;
		for(int i=1;i<=m;i++)c[i]+=c[i-1];
		for(int i=n;i>=1;i--)sa[c[rr[rr2[i]]]--]=rr2[i],rr2[i]=0; //rr2[i]不能写成i,因为是按rr2[1~n]在排序 
		cnt=0;
		swap(rr,rr2);//更新rr的值，暂时将rr放到rr2中 
		rr[sa[1]]=++cnt;
		for(int i=2;i<=n;i++){
			if(rr2[sa[i]]==rr2[sa[i-1]]&&rr2[sa[i]+k]==rr2[sa[i-1]+k])rr[sa[i]]=cnt;//是sa[i],因为rr[i]的i的意义为a的下标 
			else rr[sa[i]]=++cnt;
		}
		if(cnt==n)break;//排名均不相同 
		m=cnt;
	}
	for(int i=1;i<=n;i++)cout<<sa[i]<<" ";
	cout<<endl;
	return 0;
}

原理：

直接排序是O(n2)级别。。。

利用倍增思想，每次给以i为起始，长度为k(k倍增)的区间排序。

排序过程

当每次k倍增时，可以发现只需要对其的两个关键字进行基数排序即可。

第一个关键字为rank[i]，第二个关键字为rank[i+k]如果没有，说明已经排好序，为0。

rank自然也求出来了：$rank[sa[i]]=i$

求h[i]:

定理：$h[i] \geq h[i-1]-1$

证明：(不严谨)

假如 $ra[rank[i]-1]=ra[rank[i-1]-1]$ （即 $h[i]$ 与 $h[i-1]$ 要匹配的后缀相同）

则若 $h[i-1]$ 相当于后缀 $a$~$n$ 与 $b$~$n$ 匹配，

$h[i]$ 相当于后缀 $a$~$n$ 与 $b+1$~$n$ 匹配（因为只是前进了一位）

此时 $h[i]=h[i-1]-1$

而我们知道，上述假设是不可能成立的，$rank[i]-1$ 不可能与 $rank[i-1]-1$ 相同

所以 $ra[rank[i-1]-1]$ 只是可能与 $ra[i]$ 排名相邻

根据$height$数组的性质，排名相邻的匹配最大。

所以 $h[i] \geq h[i-1]-1 $

代码：

(rr为rank,hi为h)

	for(int i=1;i<=n;i++){
		int j=sa[rr[i]-1];
		int tt=hi[i-1]-1;
		if(tt<0)tt=0;
		hi[i]=tt;
		for(int l1=i+tt,l2=j+tt;l1<=n,l2<=n;l1++,l2++){
			if(a[l1]!=a[l2])break;
			hi[i]++;
		}
	}

height也出来了。