后缀数组
在字符串处理当中,后缀树和后缀数组都是非常有力的工具。
其实后缀数组是后缀树的一个非常精巧的替代品,它比后缀树
不太逊色,并且,它比后缀树所占用的空间小很多。可以说,
在信息学竞赛中后缀数组比后缀树要更为实用。
不知道后缀数组是撒 百度
后缀数组(SA)是 “ 排第几的是谁? ” ,
名次数组(RANK)是 “ 你排第几? ”
图解过程
注释版
#include <stdio.h>
#include <string.h>
#define N 1001
int SA[N],heigt[N],c[N], rank[N], X[N], Y[N];
//后缀数组 前缀数组 辅助数组(计数排序)名次数组 关键1序 关键2序
int cmp(int *r,int a,int b,int l)
{ return r[a]==r[b]&&r[a+l]==r[b+l];
}
void gethzsz(int *r,int n)
{
int i,j,p,m=127;int *tem,*x=X,*y=Y;//x y分别代表数组X Y的首地址
for(i=0;i<m;i++)c[i]=0; //计数排序法
for(i=0;i<n;i++)
c[r[i]]++,x[i]=r[i];
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--) SA[--c[x[i]]]=i;//得到初始SA
for(j=1;j<=n;j<<=1)// j代表当前所求长度
{
for(p=0,i=n-j;i<n;i++)y[p++]=i;//将后缀长度小于等于当前长度的放在
for(i=0;i<n;i++)
if(SA[i]>=j)y[p++]=SA[i]-j;//后移操作 在第一关键序的基础上排第二关键序
for(i=0;i<m;i++)c[i]=0; //实质是 因为第一关键序字串后移当前长度直接作为第二关键序
for(i=0;i<n;i++)c[x[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)
SA[--c[x[y[i]]]]=y[i];//按第二关键字排序
tem=x;x=y;y=tem;x[SA[0]]=0;p=1;
for(i=1;i<n;i++)
x[SA[i]]=cmp(y,SA[i],SA[i-1],j)?p-1:p++;
if(p>n)break;
m=p;
}
}
void getheigt(int *r ,int n)
{
int i,j,k=0; heigt[0]=0;
for(i=0;i<n;i++)rank[SA[i]]=i;
for(i=0;i<n;i++)
{
if(!rank[i])continue;//排除 0首项
if(k)--k;
j=SA[rank[i]-1];//j=当前一个名次字串前一个字串( 看是否位该串前缀)
while(i+k<n&&j+k<n&&r[i+k]==r[j+k])k++;
heigt[rank[i]]=k;//当前坐标 的前缀
}
}
int main()
{ char str[N];int len,i,j;int r[N];
while(scanf("%s",&str)!=EOF)
{
len=strlen(str);
for(i=0;i<len;i++)r[i]=str[i];
gethzsz(r,len);
getheigt(r,len);
puts("--------------All Suffix--------------");
for(i=0; i<len; ++i)
{
printf("%d:\t",i);
for(int j=i-1; j<len; ++j)
printf("%c",str[j]);
puts("");
}
puts("");
puts("-------------After sort---------------");
for(i=0; i<len; ++i)
{
printf("SA[%2d ] = %2d\t",i,SA[i]+1);
for(j=SA[i]; j<len; ++j)
printf("%c",str[j]);
puts("");
}
puts("");
puts("---------------Height-----------------");
for(i=0; i<len; ++i)
printf("height[%2d ]=%2d \n",i,heigt[i]);
puts("");
puts("----------------Rank------------------");
for(i=0; i<len; ++i)
printf("Rank[%2d ] = %2d\n",i,rank[i]+1);
puts("------------------END-----------------");
}
return 0;
}
//4 5 6 1 7 2 8 3
//4 6 8 1 2 3 5 7
//1 4 3 4 2 3 1 2
半压缩版
#include<stdio.h>
#include<string.h>
#define N 1001
int X[N],Y[N],SA[N],heigt[N],c[N],rank[N];
int cmp(int *r,int a,int b,int l){return r[a]==r[b]&&r[a+l]==r[b+l];}
void gethzsz(int *r,int n)
{ int i,j,p,m=120;int *tem,*x=X,*y=Y;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[i]=r[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)SA[--c[x[i]]]=i;
for(j=1;p<=n;j<<=1,m=p)
{
for(p=0,i=n-j;i<n;i++)y[p++]=i;
for(i=0;i<n;i++)if(SA[i]>=j)y[p++]=SA[i]-j;
for(i=0;i<m;i++)c[i]=0;
for(i=0;i<n;i++)c[x[i]]++;
for(i=1;i<m;i++)c[i]+=c[i-1];
for(i=n-1;i>=0;i--)SA[--c[x[y[i]]]]=y[i];
tem=x;x=y;y=tem;x[SA[0]]=0;p=1;
for(i=1;i<n;i++)x[SA[i]]=cmp(y,SA[i],SA[i-1],j)?p-1:p++;
}
}
void getheigt(int *r,int n)
{int i,j,k=0; heigt[0]=0;
for(i=0;i<n;i++)rank[SA[i]]=i;
for(i=0;i<n;i++)
{ if(!rank[i])continue;
if(k)k--;j=SA[rank[i]-1];
while(i+k<n&&j+k<n&&r[i+k]==r[j+k])k++; heigt[rank[i]]=k;
}
}
int main()
{
char str[N];int i,j,len;int r[N];
while(scanf("%s",&str)!=EOF)
{
len=strlen(str);
for(i=0;i<len;i++)r[i]=str[i];
gethzsz(r,len);
getheigt(r,len);
for(i=0;i<len;i++)printf("%2d",SA[i]+1);printf("\n");
for(i=0;i<len;i++)printf("%2d",rank[i]+1);printf("\n");
for(i=0;i<len;i++)printf("%2d",heigt[i]);printf("\n");
}
return 0;
}