后缀数组实现错误

我编写了一个后缀数组实现，并在我的实现中发现了一个问题。具体我已经输出的第一少数后缀数组居此string的RA[0..7]（长度= 10^5）并具有下面的输出：后缀数组实现错误

但是正确的一个必须是（一切由23移位）：

我知道如何解决它的两种方法，但我不知道它为什么起作用。

第一种方式是添加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; 
}

来源

2014-06-18 Gary Ye

我没有被问到错误的问题（一些SOers会这样做），但您必须通过查找触发它的*最小可能*输入来做出努力。 –

（寻找触发错误的小输入是您在*尝试自行修复它的过程中应该做的第一件事情。） –

随机测试有助于查找小问题输入。 –

在下面的行：
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-18 18:21:39 kraskevich

这是真的。我通过使用一个非常简单的测试用例（我无法随机生成...）验证了这一点： abab 所得后缀数组是 0：ABAB 2：AB 3：乙 1：BAB 这显然是错误的。 –

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

“坏” 的代码行是：

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，并且此代码崩溃。

来源

2014-06-19 20:23:15

后缀数组实现错误

回答

相关问题