后缀数组实现bug

Question

我已经编写了后缀数组实现，并在我的实现中发现了一个问题。具体地说，我已经输出了这个字符串(长度= 10^5)的前几个后缀数组排名RA[0..7]，并有以下输出:

80994
84360
87854
91517
95320
99277
83068

但正确的必须是(所有移动了23):

81017
84383
87877
91540
95343
99300
83091

我知道两种方法来修理它，但我不知道为什么它工作。

第一种方法是将S[N++] = '$';添加到buildSA()函数的顶部(然后输出比正确的少1，但没关系)

我还找到了另一个解决方案，将MAX_N常数减小到1e5 + 10!

这对我来说太神奇了，我真的需要知道为什么会出现这个错误，因为我不想再出现这个错误。

#include <cstdio>
#include <cstring>
#include <algorithm>
using std::max;
const int MAX_N = 2e5 + 10;
int SA[MAX_N];   // The ith element is the index of the suffix
int RA[MAX_N];   // The rank of the suffix at i
int tmp[MAX_N];  // A temporary array
int B[MAX_N];    // An array for the buckets
int N;
char S[MAX_N];
void bucketSort(int k){
  int i, m = max(256, N);
  for(i = 0; i < m; i++)
    B[i] = 0;
  for(i = 0; i < N; i++)
    B[i + k < N ? RA[i + k] : 0] ++;
  for(i = 1; i < m; i++)
    B[i] += B[i - 1];
  for(i = N - 1; i >= 0; i--)
    tmp[--B[SA[i] + k < N ? RA[SA[i] + k] : 0]] = SA[i];
  for(i = 0; i < N; i++)
    SA[i] = tmp[i];
}
void buildSA(){
  for(int i = 0; i < N; i++){
    SA[i] = i;
    RA[i] = S[i];
  }
  for(int k = 1; k < N; k <<= 1){
    bucketSort(k);
    bucketSort(0);
    int norder = 0;
    tmp[SA[0]] = 0;
    for(int i = 1; i < N; i++){
      if(RA[SA[i]] == RA[SA[i - 1]] && RA[SA[i] + k] == RA[SA[i - 1] + k])
      {} else norder++;
      tmp[SA[i]] = norder;
    }
    for(int i = 0; i < N; i++)
      RA[i] = tmp[i];
    if(norder == N)
      break;
  }
}
void printSA(){
  for(int i = 0; i < N; i++){
    printf("%d: %sn", SA[i], S + SA[i]);
  }
}
int main(){
  scanf("%s", S);
  N = strlen(S);
  buildSA();
  for(int i = 0; i < 7; i++){
    printf("%dn",RA[i]);
  }
  return 0;
}

Answer 1

下一行:
if(RA[SA[i]] == RA[SA[i - 1]] && RA[SA[i] + k] == RA[SA[i - 1] + k])
SA[i] + k可以>= N (SA[i - 1] + k也一样)。
应该改成(SA[i] + k) % N

Answer 2

我想我是浪费了很多时间才拿到的。有时即使是最小的错误也会导致错误的答案。

"坏"代码行是:

if(RA[SA[i]] == RA[SA[i - 1]] && RA[SA[i] + k] == RA[SA[i - 1] + k])
      {} else norder++;

我通过使用一个非常简单的测试用例(我不能随机生成…)验证了这一点:

abab

结果后缀数组为

0: abab
2: ab
3: b
1: bab

显然是错误的

在步骤k = 2时，如果我们比较两个后缀，如ab和abab，那么我们意识到它们具有相同的秩，因为它们的第一个k = 2个字符匹配。ab是后缀#2，加上k = 2，我们就超出了范围。

我经常这样编码

，因为我总是附加一个辅助字符(例如:'$')到最后。如果我不放这样一个字符(就像我的例子)，SA[I] + k实际上可能>= N，这段代码会崩溃。