应该增加这个abababab或者类似的数据。
我的一份代码输入abababab这个字符串后,输出的结果是1 3 5 7 8 6 4 2,然而正确的是7 5 3 1 8 6 4 2。没想到我提交这份代码后AC了。。。。
附上错误的代码
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
typedef long long ll;
const int MAXN = 1e6+5;
int c[MAXN],t1[MAXN],t2[MAXN],sa[MAXN];
void getSA(char str[],int m)
{
int *x=t1,*y=t2;
for(int i=0;i<m;++i) c[i]=0;
int n=0;
for(int i=0;str[i];++i){
++n;
c[x[i]=str[i]]++;
}
// x[n]=m;
// y[n]=m;//增加这两行代码就正确了
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;
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=0;
x[sa[0]]=p++;
for(int i=1;i<n;++i){
x[sa[i]]=(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k>=n?n:sa[i]+k]==y[sa[i-1]+k>=n?n:sa[i-1]+k]?p-1:p++);
}
if (p>=n) break;
m=p;
}
}
char str[MAXN];
int main()
{
scanf("%s",str);
getSA(str,256);
for(int i=0;str[i];++i)
printf("%d ",sa[i]+1);
return 0;
}