後綴數組實現錯誤

我編寫了一個後綴數組實現，並在我的實現中發現了一個問題。具體我已經輸出的第一少數後綴數組居此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

後綴數組實現錯誤

回答

相關問題