字符串-后缀数组
标签：方法 cstring main 不能 mes 数组 字符串 元素 序号
倍增法，每次排2^j长度的段，转移就是双关键字排序就好啦！
求height可以利用height[rank[i]]>=height[rank[i-1]]-1的性质，当然证明考虑构造，并反证，假设在其中插入元素使性质不成立，推矛盾就可以了。
基本上是从网上抄来的模板啦，解释一下代码吧~
x在交换之前充当了rank的功能。
关于c的用处，来看计数排序的实现方法：
for(i=1;i){
scanf("%d",&a[i]);
++c[a[i]];
}
for(i=1;i)
c[i]+=c[i-1];
for(i=n;i;i--)
p[c[a[i]]--]=i;
for(i=1;i)
printf("%d",a[p[i]]);
y是按后半部分排序后前半部分开头序号，即x[y[i]+j]是单调的。
#include
#include
#includeusing namespace std;
const int N=1e6+6;
char s[N];
int t1[N],t2[N],c[N];
int sa[N],rk[N],ht[N];
void gtsa(int n,int m){
int i,j,p=0,*x=t1,*y=t2;
for(i=1;i)
++c[x[i]=s[i]];
for(i=1;i)
c[i]+=c[i-1];
for(i=n;i;i--)
sa[c[x[i]]--]=i;
for(i=1;i)
c[i]=0;
for(j=1;j1){
p=0;
for(i=n-j+1;i)
y[++p]=i;
for(i=1;i)
if(sa[i]>j)
y[++p]=sa[i]-j;
for(i=1;i)
++c[x[y[i]]];
for(i=1;i)
c[i]+=c[i-1];
for(i=n;i;i--)
sa[c[x[y[i]]]--]=y[i];
for(i=1;i)
c[i]=0;
swap(x,y);
p=1;
x[sa[1]]=1;
for(i=2;i)
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j])?p:++p;
m=p;
}
for(i=1;i)
rk[sa[i]]=i;
p=0;
for(i=1;i){
j=sa[rk[i]-1];
if(p)--p;
while(s[i+p]==s[j+p])++p;
ht[rk[i]]=p;
}
}
int main()
{
scanf("%s",s+1);
int l=strlen(s+1);
gtsa(l,127);return 0;
}
如果实在不能理解，可以先看一下这份冗长而低效的方法：
#include
#include
#includeusing namespace std;
const int N=3e5+5;
char s[N];
int sa[N],rk[N],ht[N];
struct elm{
int x,r1,r2;
bool operator==(elm a)const{
return r1==a.r1&&r2==a.r2;
}
}p[N],q[N];
int sm[N];
void gtsa(int n,int m){
int i,j;
for(i=1;i)
p[i]=(elm){i,s[i],0};
for(i=1;i)
sm[i]=0;
for(i=1;i)
++sm[p[i].r2];
for(i=1;i)
sm[i]+=sm[i-1];
for(i=n;i;i--)
q[sm[p[i].r2]--]=p[i];
for(i=1;i)
p[i]=q[i];
for(i=1;i)
sm[i]=0;
for(i=1;i)
++sm[p[i].r1];
for(i=1;i)
sm[i]+=sm[i-1];
for(i=n;i;i--)
q[sm[p[i].r1]--]=p[i];
for(i=1;i)
p[i]=q[i];
m=1;
q[1].r1=m;
for(i=2;i)
q[i].r1=(p[i]==p[i-1]?m:++m);
for(i=1;i)
p[i]=q[i];
for(j=1;j1){
for(i=1;i)
sm[i]=0;
for(i=1;i)
++sm[p[i].x];
for(i=1;i)
sm[i]+=sm[i-1];
for(i=n;i;i--)
q[sm[p[i].x]--]=p[i];
for(i=1;i)
p[i]=q[i];
for(i=n-j+1;i)
p[i].r2=0;
for(i=1;i)
p[i].r2=p[i+j].r1;
for(i=1;i)
sm[i]=0;
for(i=1;i)
++sm[p[i].r2];
for(i=1;i)
sm[i]+=sm[i-1];
for(i=n;i;i--)
q[sm[p[i].r2]--]=p[i];
for(i=1;i)
p[i]=q[i];
for(i=1;i)
sm[i]=0;
for(i=1;i)
++sm[p[i].r1];
for(i=1;i)
sm[i]+=sm[i-1];
for(i=n;i;i--)
q[sm[p[i].r1]--]=p[i];
for(i=1;i)
p[i]=q[i];
m=1;
q[1].r1=m;
for(i=2;i)
q[i].r1=(p[i]==p[i-1]?m:++m);
for(i=1;i)
p[i]=q[i];
}
for(i=1;i)
sa[i]=p[i].x,
rk[p[i].x]=i;
for(i=1,j=0;i){
if(j)--j;
while(s[i+j]==s[sa[rk[i]-1]+j])
++j;
ht[rk[i]]=j;
}
}
int main()
{
scanf("%s",s+1);
int l=strlen(s+1);
gtsa(l,127);
for(int i=1;i)
printf("%d ",sa[i]);
return 0;
}
更高效的算法请右转后缀自动机……
字符串-后缀数组
标签：方法 cstring main 不能 mes 数组 字符串 元素 序号
原文地址：https://www.cnblogs.com/l-ly-03/p/String-SuffixArray.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
字符串-后缀数组
文章链接：http://soscw.com/essay/24100.html
评论