string - 后缀数组实现错误

Question

我编写了一个后缀数组实现，并在我的实现中发现了一个问题。具体来说，我已经输出了这个 string 的前几个后缀数组等级 RA[0..7] (length = 10^5) 并有以下输出:

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: %s\n", SA[i], S + SA[i]);
  }
}

int main(){
  scanf("%s", S);
  N = strlen(S);
  buildSA();
  for(int i = 0; i < 7; i++){
    printf("%d\n",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。