题目：后缀排序

什么是后缀数组？他主要包含两个数组：sa和rk。

其中sa[i]表示将字符串后缀排序后第i小的编号，rk[i]表示后缀i的排名。

显然sa[rk[i]]=i,rk[sa[i]]=i。

例如字符串aba，他的后缀aba,ba,a，排序后a,aab,ab，此时

| i | 1 | 2 | 3 |

| sa | 3 | 1 | 2 |

| rk | 2 | 3 | 1 |

观察上面给出的式子，发现都成立。

那如何求后缀数组呢，最简单的方法是直接排序，不要以为时间复杂度是O(nlogn)，字符串比较还有一层O(n)，所以总时间复杂度是O(n^2logn)的，显然不行。

既然快排不行，那用别的排序咯，我们发现字符个数很少，因此采用基数排序，但是朴素的基数排序是O(n^2)更慢了，因此这里使用倍增优化，每次枚举范围扩大一倍，为什么可行？

试想一下，如果对于基数排序，我们也可以通过压位，以10，100，甚至更多为一个单位，显然答案不会改变，只是效率的改变罢了，因此这里同理可以得到。

具体讲一下做法，设字符串s，先求出所有s[i]的排名，这就是最基础的对应关系，也就是以一个字符为基准的方法个数，接下来就是枚举长度了，每次求出二元组(k1[i],k2[i])表示排序的两个关键字，以k2[i]为关键字排序，然后再以k1[i]为关键字排，排序号后，求出所有数的排名，如果最大的编号为字符串长度，那么就说明已经完成了后缀排序，此时sa和rk中存储的就是最开始所说的内容。

时间复杂度O(nlogn)，一个比较优秀的算法。

代码：

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <algorithm>

const int N=1e6+5;

using namespace std;

int n,cnt[N],rk[N],psa[N],sa[N],k1[N],k2[N],m;

char s[N];

int main()

{

	scanf("%s",s);

	n=strlen(s);

	m=max(n,300);

	for(int i=0;i<n;i++)

	    cnt[(int)s[i]]++;

	for(int i=1;i<m;i++)

	    cnt[i]+=cnt[i-1];

	for(int i=0;i<n;i++)

	    rk[i]=cnt[(int)s[i]]-1;

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

	{

		for(int i=0;i<n;i++)

		{

			if(i+w>=n)

			    k2[i]=0;

			else

			    k2[i]=rk[i+w];

			k1[i]=rk[i];

		}

		for(int i=0;i<n;i++)

		    cnt[i]=0;

		for(int i=0;i<n;i++)

		    cnt[k2[i]]++;

		for(int i=1;i<m;i++)

		    cnt[i]+=cnt[i-1];

		for(int i=n-1;i>=0;i--)

		    psa[--cnt[k2[i]]]=i;

		for(int i=0;i<n;i++)

		    cnt[i]=0;

		for(int i=0;i<n;i++)

		    cnt[k1[i]]++;

		for(int i=1;i<m;i++)

		    cnt[i]+=cnt[i-1];

		for(int i=n-1;i>=0;i--)

		    sa[--cnt[k1[psa[i]]]]=psa[i];

		int tmp=1;

		rk[sa[0]]=1;

		for(int i=1;i<n;i++)

		    if(k1[sa[i]]==k1[sa[i-1]] && k2[sa[i]]==k2[sa[i-1]])

		        rk[sa[i]]=tmp;

		    else

		        rk[sa[i]]=++tmp;

		if(tmp==n)

		    break;

	}

	for(int i=0;i<n;i++)

	    printf("%d ",sa[i]+1);

	return 0;

}

巴特西

2022春每日一题：Day 13

题目：后缀排序

最新文章

热门文章