后缀数组（修订版）

2019-11-06 07:44:56

字体：大中小

来源：转载

供稿：网友

今天在码一道后缀数组+二分答案时，调了一个上午，发现后缀数组出了问题，这就像最信任的人给了泥最致命的一刀QAQ~~~原来蓝书上的板子是有问题的，因为若以0为下标,由于初始值是0，在重新计算x数组时，会造成越界，原本越界的字符串（空字符串）应该当做最小的（-1？？？）来比较，而这样会造成错误。

hack数据： cbcbc 若用蓝书上的板子，sa数组为这里写图片描述实际上应该为要完善程序，只需加上一个初始化，将x、y数组变为-1即可…… 原代码： http://blog.csdn.net/moon1125666900/article/details/54809904 修改后：

//bzoj 1031#include <cstdio>#include <algorithm>#include <iostream>#include <string>#include <cstring>#define maxn 200005using namespace std;string ans,s;int n,c[maxn],sa[maxn],t2[maxn],t1[maxn],h[maxn],rank[maxn];int *x=t1,*y=t2;void get_sa(){ int m=257; memset(t1,-1,sizeof(t1));//新加内容，非常重要！！！！！ memset(t2,-1,sizeof(t2)); for (int i=0;i<m;i++) c[i]=0; for (int i=0;i<n;i++) c[x[i]=sa[i]]++; for (int i=1;i<m;i++) c[i]+=c[i-1]; for (int i=n-1;i>=0;i--) sa[--c[x[i]]]=i; for (int k=1;k<=n;k<<=1) { int p=0; for (int i=n-k;i<n;i++) y[p++]=i;//第二关键字排序 for (int i=0;i<n;i++) if (sa[i]>=k) y[p++]=sa[i]-k;//sa[i]>=k则有第二关键字，否则没有y for (int i=0;i<m;i++) c[i]=0;//第一关键字排序 for (int i=0;i<n;i++) c[x[y[i]]]++; for (int i=1;i<m;i++) c[i]+=c[i-1]; for (int i=n-1;i>=0;i--) sa[--c[x[y[i]]]]=y[i]; swap(x,y); p=1;x[sa[0]]=0; for (int i=1;i<n;i++) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++; if (p>=n) break; m=p; }}void get_h(){ int k=0,j; for (int i=0;i<n;i++) rank[sa[i]]=i; for (int i=0;i<n;h[rank[i++]]=k) for (k?k--:0,j=sa[rank[i]-1];s[i+k]==s[j+k];k++);}int main(){ cin>>s; //s=s+s; n=s.length(); for (int i=0;i<n;i++) sa[i]=s[i]; get_sa(); get_h(); for (int i=0;i<n;i++) PRintf("%d ",sa[i]); return 0;}

上一篇：SpringMVC实现图片上传

下一篇：PIC单片机-RS232串口通信

学习交流

索泰发布一款GTX 1070 Mini迷你版本:小机

索泰发布一款GTX 1070 Mini迷你版本:小机箱大爱...

热门图片

猜你喜欢的新闻

猜你喜欢的关注