4

我编写了一个 Suffix Array 实现并在我的实现中发现了一个问题。具体来说，我输出了RA[0..7]该字符串的前几个后缀数组等级（长度 = 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;
}
4

2 回答 2

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。

于 2014-06-18T18:21:39.973 回答
0

我想我在浪费了很多时间之后得到了它。有时，最小的错误可能会导致错误的答案。

“坏”的代码行是：

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 步，如果我们比较两个像 then 这样的后缀ab，abab我们意识到它们具有相同的等级，因为它们的前 k = 2 个字符匹配。ab是后缀#2，加上k = 2，我们就超出了范围。

我经常这样编码，因为我总是在末尾附加一个辅助字符（例如'$'）。如果我不输入这样的字符（就像我的情况一样）， SA[i] + k 实际上可能 >= N 并且此代码崩溃。

于 2014-06-19T20:23:15.783 回答