后缀排序
标签：char bool 排序 tmp scan pre efi span cst
后缀数组板子，给出一个字符串，要求输出sa数组。
首先声明一下各数组的作用。
rank:序列上的点->点权;
sa:排名->位置;
tmp:辅助数组;
#include
#include#define N 1000050
int rank[N],tmp[N],sa[N],hs[N],num[N];
int n;
char s[N];
bool cmp(int i,int j,int k)
{
if(i+k>n||j+k>n)return 0;
return rank[i]==rank[j]&&rank[i+k]==rank[j+k];
}
int main()
{
scanf("%s",s+1);
n = strlen(s+1);
int i,cnt=0;
for(i=1;is[i];
for(i=1;i;
for(i=1;i200;i++)if(hs[i])tmp[i]=++cnt;
for(i=1;i200;i++)hs[i]+=hs[i-1];
for(i=1;ii;
for(int k=1;cnt!=n;k1)
{
for(i=1;i0;
for(i=1;i;
for(i=1;i1];
for(i=n;i>=1;i--)if(sa[i]>k)tmp[sa[i]-k]=hs[rank[sa[i]-k]]--;
for(i=1;i1]=hs[rank[n-i+1]]--;
for(i=1;ii;
for(i=1,cnt=0;i1],k)?cnt:++cnt;
for(i=1;itmp[i];
}
for(i=1;i"%d ",sa[i]);
printf("\n");
return 0;
}
后缀排序
标签：char bool 排序 tmp scan pre efi span cst
原文地址：https://www.cnblogs.com/LiGuanlin1124/p/9670985.html
文章来自：
搜素材网的
编程语言模块，转载请注明文章出处。
文章标题：
后缀排序
文章链接：http://soscw.com/index.php/essay/97937.html
评论