初学后缀数组

后缀排序

Description

Tim正在自学《数据结构》,他刚刚学会如何比较两个字符串大小。书上是这么说的(和Pascal语言中的比较规则相同,学习过Pascal语言的同学可以跳过这段): 
比较两个不同字符串s1=’p1p2p3…pN’和s2=’q1q2q3…qM’的大小,设N<=M。 
若s1是s2的前缀,则s1<s2。否则设pi<>qi,且i最小;若pi<qi,则s1<s2,否则s1>s2。 
Tim想通过练习熟练运用这个规则,于是打算出许多字符串,并将它们从小到大排序。可是Tim非常懒,随机写出 K个很长的字符串实在是太麻烦了。不过聪明的他想到了一个好办法,他写了一个很长的字符串,自言自语说,“我只要把这个字符串的所有后缀从小到大排序就可以了”。 

Input

输入文件suffix.in中仅有一行,且是一个仅包含小写字母的字符串,长度K不超过10^5。 

Output

有K行,每行一个数字,第i行的数字Pi表示所有后缀中,第i小的是由原字符串第Pi个字符引导的后缀。 

Sample Input

 

mississippi

 

Sample Output

 

11
8
5
2
1
10
9
7
4
6
3

 

Source

Oibh(后缀数组)

 

 

后缀数组:后缀数组SA 是一个一维数组,它保存1..n 的某个排列SA[1],SA[2],……,SA[n],并且保证Suffix(SA[i]) < Suffix(SA[i+1]),1≤i<n。

 

也就是将S 的n 个后缀从小到大进行排序之后把排好序的后缀的开头位置顺次放入SA 中。

 

名次数组:名次数组Rank[i]保存的是Suffix(i)在所有后缀中从小到大排列的“名次”。

 

倍增算法求后缀数组的主要思路是:用倍增的方法对每个字符开始的长度为2k 的子字
符串进行排序,求出排名,即rank 值。k 从0 开始,每次加1,当2k 大于n 以
后,每个字符开始的长度为2k 的子字符串便相当于所有的后缀。并且这些子字
符串都一定已经比较出大小,即rank 值中没有相同的值,那么此时的rank 值就
是最后的结果。每一次排序都利用上次长度为2k-1 的字符串的rank 值,那么长
度为2k 的字符串就可以用两个长度为2k-1 的字符串的排名作为关键字表示,然
后进行基数排序,便得出了长度为2k 的字符串的rank 值。以字符串“aabaaaab”
为例,整个过程如图2 所示。其中x、y 是表示长度为2k 的字符串的两个关键字。

 

 

 

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define maxn 100010
using namespace std;
char s[maxn];
int n,m,tot,sum[maxn],t1[maxn],t2[maxn],rank[maxn],SA[maxn];
void get_SA(){
	int *x=t1,*y=t2;
	for (int i=1;i<=n;i++) sum[x[i]=s[i]]++;
	for (int i=1;i<=255;i++) sum[i]+=sum[i-1];
	for (int i=1;i<=n;i++) SA[sum[x[i]]--]=i;
	tot=0;
	for (int len=1;tot<n;len<<=1,m=tot){
		tot=0;
		for (int i=n-len+1;i<=n;i++) y[++tot]=i;
		for (int i=1;i<=n;i++) if (SA[i]>len) y[++tot]=SA[i]-len;
		for (int i=1;i<=m;i++) sum[i]=0;
		for (int i=1;i<=n;i++) sum[x[y[i]]]++;
		for (int i=1;i<=m;i++) sum[i]+=sum[i-1];
		for (int i=n;i>=1;i--) SA[sum[x[y[i]]]--]=y[i];
		swap(x,y);
		x[SA[1]]=tot=1;
		for (int i=2;i<=n;i++){
			if (y[SA[i]]!=y[SA[i-1]]||y[SA[i]+len]!=y[SA[i-1]+len]) tot++;
			x[SA[i]]=tot;
		}
	}
	for (int i=1;i<=n;i++) rank[i]=x[i];
}
int main(){
	scanf("%s",s+1);
	n=strlen(s+1),m=123;
	get_SA();
	for (int i=1;i<=n;i++) printf("%d\n",SA[i]);
	return 0;	
}

 

郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。