求后缀数组的rank[],sa[]
- 思路倍增优化
||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|第0次排序|a|a|a|b|b|b|b|c|c|c|c|0|倍增|
|第1次排序|aa|aa|ab|bb|bb|bb|bc|cc|cc|cc|c0|0a|\(2^0\)|
|第2次排序|aaaa|aaab|abbb|bbbb|bbbb|bbbc|bccc|cccc|cccc|ccc0|c00a|0aaa|\(2^1\)|
|第...次排序|...|...|...|...|...|...|...|...|...|...|...|...|\(2^{...}\)|
- 以上一次排序为第一关键字,排序后的后一位(即字符串中s[i+\(2^k\)])为第二关键字
- 越界的\(i+2^k\)即可用后缀0进行处理,就可以将每一个后缀子串进行基数排序
- 其中一种高效程序如下所示,详见代码
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cmath>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;
const int Max=1000001;
string s;int n;
int rnk[Max],sa[Max];
int tmp[Max],c[Max];
void sarank()
{
int na=256;//ASCII码中最大值是256
memset(c,0,na*sizeof(int));//给C数组清零
n=s.size();//取出字符串的长度
s[n]=0;n++;//在字符串后加一个后缀,方便倍增优化和比较
for(int i=0; i<n; i++)
{
rnk[i]=(int)s[i];//每个字符的字典序即为初始排名
c[rnk[i]]++;//记录每个排名的个数
}//初始化rank[]名次
//类似于以下排名模式
//a a a b b b b c c c c 0
//1 1 1 2 2 2 2 3 3 3 3 0
for(int i=1; i<na; i++) c[i]=c[i]+c[i-1];
//求前缀和,此时c[]数组即为第i个字符(或字符串)的排名
//类似于以下排名模式,算并列之后的最小名次
//a a a b b b b c c c c 0
//3 3 3 7 7 7 7 11 11 11 11 1
for(int i=0; i<n; i++)//循环字符串0~n-1
sa[--c[rnk[i]]]=i;
//按照从左到右该字符串由大到小（也可以由小到大）的顺序给字符串排名
//sa[]类似于以下排名模式,名次从零开始
//a a a b b b b c c c c 0
//2 1 0 6 5 4 3 10 9 8 7 0
//此时c[]数组又为第i个字符(或字符串)的排名
//类似于以下排名模式
int j;
for(int len=1; len<n; len=len<<1)//倍增
{
for(int i=0; i<n; i++)//循环名次0~n-1
{
j=sa[i]-len;//下一次字符的位置
if(j<0) j=j+n;//由于加入后缀,越界的第二关键字相当于赋为零
tmp[c[rnk[j]]++]=j;
//第一关键字名次已经得出,即为下表c[],每次++即可得到第二关键字的总排名
}
//此时,按照从左到右该字符串由小到大的顺序给字符串排名
//tmp[]类似于以下排名模式,名次从零开始,记录下标
//rank[]a a a b b b b c c c c 0
// 1 1 1 2 2 2 2 3 3 3 3 0
//c[] a a a b b b b c c c c 0
// 0 0 0 3 3 3 3 7 7 7 7 0
//tmp[] aa aa ab bb bb bb bc cc cc cc c0 0a
// 0 1 2 3 4 5 6 7 8 9 0 0
sa[tmp[c[0]=0]]=j=0;//排名第0的总排名第0
for(int i=1; i<n; i++)//
{
if(rnk[tmp[i]]!=rnk[tmp[i-1]]||rnk[tmp[i]+len]!=rnk[tmp[i-1]+len])
//如果第一关键字和第二关键字不同,必为下一名次
c[++j]=i;//预处理,本次总排名即为下一次第一关键字的排名
sa[tmp[i]]=j;//排名第tmp[i]的总排名第j
}
//此时sa[]类似于以下排名模式,上一个循环相当于错开名次
//sa[] aa aa ab bb bb bb bc cc cc cc c0 0a
// 0 1 2 3 3 3 4 5 5 5 0 0
memcpy(rnk,sa,n*sizeof(int));
memcpy(sa,tmp,n*sizeof(int));
//依据后缀数组的定义,此时sa[]相当于rank[],tmp[]相当于sa[],交换赋值
if(j>=n-1) break;//如果名次全不相同,已经求完了
}
}
int main()
{
cin>>s;//输入字符串
sarank();//求sa[],rank[]
cout<<"sa[i]:";for(int i=1; i<n; i++) printf("%d ",sa[i]+1);printf("\n");
//注意下标 1~n sa[0]是后缀,由于下标从零开始,下标+1
cout<<"rnk[i]:";for(int i=0; i<n-1; i++) printf("%d ",rnk[i]);printf("\n");
//注意下标 0~n-1 rnk[n-1]是后缀,由于名次从零开始,但后缀占一个名次,不用加1
return 0;
}