SA 后缀数组

时间：2023-03-09 06:00:51
SA 后缀数组

SA 后缀数组

首先一定要确定\(SA\)是个什么东西

\(SA[i]\)表示的是排名为\(i\)的后缀是哪一个

至于后缀\(i\)的排名是多少，那个是\(rank[i]\)

当然啦

最最最难懂的就是基数排序

要是不用基数排序，每次对于一个二元组直接\(sort\)一下

这样的复杂度是\(O(nlog^2)\)

对于二元组的基数排序应该是这样做的：

首先把所有元素按照最后一维丢到依次对应的桶里面

然后顺次取出

再按照第一维依次丢入

再顺次取出

这样就可以排序啦

先把代码丢出来

bool cmp(int i,int j,int k){return y[i]==y[j]&&y[i+k]==y[j+k];}

void GetSA()

{

	int m=30;

	for(int i=1;i<=n;++i)t[x[i]=a[i]]++;

	for(int i=1;i<=m;++i)t[i]+=t[i-1];

	for(int i=n;i>=1;--i)SA[t[x[i]]--]=i;

	for(int k=1;k<=n;k<<=1)

	{

		int p=0;

		for(int i=0;i<=m;++i)y[i]=0;

		for(int i=n-k+1;i<=n;++i)y[++p]=i;

		for(int i=1;i<=n;++i)if(SA[i]>k)y[++p]=SA[i]-k;

		for(int i=0;i<=m;++i)t[i]=0;

		for(int i=1;i<=n;++i)t[x[y[i]]]++;

		for(int i=1;i<=m;++i)t[i]+=t[i-1];

		for(int i=n;i>=1;--i)SA[t[x[y[i]]]--]=y[i];

		swap(x,y);

		x[SA[1]]=p=1;

		for(int i=2;i<=n;++i)x[SA[i]]=cmp(SA[i],SA[i-1],k)?p:++p;

		if(p>=n)break;

		m=p;

	}

}

首先，第一次做\(k=0\)时

相当于每个后缀的第二维都是一样的

所以，直接按照第一维（也就是自己的值）

进行一次基数排序

接下来

每次基数排序都要利用到上一次的值

还记得吧，基数排序是先按照第二维从小往大拍

那么，我们就先把第二维的顺序搞出来

首先最小的一定就是没有第二维的东西

所以我们先把这些数直接丢进数组里面

接下来就是有第二维的东西啦

第\(i\)位的第二维是啥？\(rank[i+k]\)

所以，从小到达枚举\(SA\)，这样保证第二维从小往大

那么，只要\(SA[i]>k\)

就证明它是一个东西的第二维

所以，把\(SA[i]-k\)丢到数组里面去就好啦

这样的话，按照第二维就拍好啦

再来依次按照第一维丢到桶里面去

做一遍基数排序就好啦

这样就能够求出\(SA\)啦

看起来很简单诶。。

只是数组不要搞混了

一定搞清楚每个数组是干啥的

比如我的代码

\(SA\)是后缀数组，\(SA[i]\)表示排名为\(i\)的串是哪一个

\(rank\)相当于排名，\(rank[i]\)表示第\(i\)个串的排名

\(x,y\)两个数组是记录顺序的

分别记录第一维和第二维的排序的顺序

\(t\)是桶

这样我们就很愉快的求出了\(SA\)

还有一个数组\(Height\)

\(Height[i]\)表示串\(SA[i]\)与\(SA[i-1]\)的最长公共前缀的长度

比如说，现在要求后缀\(i\)与\(j\)的最长公共前缀

那就只需要求\(min(Height[i]),i \in [rank[i]+1,rank[j]]\)

因为已经按照字典序排好序啦

\(Height\)显然可以暴力求

但是太不优美

我们有\(Height[rank[i]]>=Height[rank[i-1]]-1\)

证明（来自\(hihoCoder\))

设\(suffix(k)\)是排在\(suffix(i-1)\)前一名的后缀，

则它们的最长公共前缀是\(height[rank[i-1]]\)

那么\(suffix(k+1)\)将排在\(suffix(i)\)的前面（这里要求\(height[rank[i-1]]>1\)，如果\(height[rank[i-1]]≤1\)，原式显然成立）

并且\(suffix(k+1)\)和\(suffix(i)\)的最长公共前缀是\(height[rank[i-1]]-1\)，

所以\(suffix(i)\)和在它前一名的后缀的最长公共前缀至少是\(height[rank[i-1]]-1\)

那么，我们按照\(rank\)的顺序来求\(Height\)就行啦

	for(int i=1;i<=n;++i)Rank[SA[i]]=i;

	for(int i=1,j=0;i<=n;++i)

	{

		if(j)j--;

		while(a[i+j]==a[SA[Rank[i]-1]+j])++j;

		height[Rank[i]]=j;

	}

我现在也不是很熟

以后多做点题我再接着补

相关文章