Boyer Moore k-不匹配算法失敗

我在一個編程網站上完成了一個字符串比較程序，其中一個不匹配。它給了我錯誤的答案。我已經廣泛地研究它，但是，我找不到代碼失敗的測試用例。有人可以提供我的代碼失敗的測試用例。我做了使用博耶·摩爾Horspool K-不匹配算法的比較，因爲它是最快的搜索算法Boyer Moore k-不匹配算法失敗

的代碼是這樣

int BMSearch_k(string text, string pattern, int tlen, int mlen,int pos) 
{  
int i, j=0,ready[256],skip2[256][mlen-1],neq; 

for(i=0; i<256; ++i) ready[i] = mlen; 
for(int a=0; a<256;a++) { 
    for(i = mlen;i>mlen-k;i--) 
    skip2[i][a] = mlen; 
}  

for(i = mlen-2;i>=1;i--) { 
    for(j=ready[pattern[i]]-1;j>=max(i,mlen-k);j--) 
     skip2[j][pattern[i]] = j-i; 
    ready[pattern[i]] = max(i,mlen-k); 
} 

j = mlen-1+pos; 
//cout<<"\n--jafffa--\n"<<pos<<"+"<<mlen<<"="<<j<<endl; 
while(j<tlen+k) { 
    //cout<<"\t--"<<j<<endl; 
    int h = j; 
    i=mlen-1; 
    int neq=0,shift = mlen-k; 

    while(i>=0&&neq<=k) { 
     //cout<<"\t--"<<i<<endl; 
     if(i>=mlen-k) 
      shift = min(shift,skip2[i][text[h]]); 
     if(text[h]!= pattern[i]) 
      neq++; 
     i--; 
     h--; 
    } 
    if(neq<=k) 
     return j-1; 
    j += shift; 
} 

return -1; 
}

來源

2012-03-08 Rama

你如何得到一個錯誤的答案，但同時找不到測試用例呢？在網站上不起作用的字符串是應該導致中斷的字符串。 – 2012-03-08 17:28:01

您沒有正確初始化您的數組，

int i, j=0,ready[256],skip2[256][mlen-1],neq; 

for(i=0; i<256; ++i) ready[i] = mlen; 
for(int a=0; a<256;a++) { 
    for(i = mlen;i>mlen-k;i--) 
    skip2[i][a] = mlen; 
}

一方面，您聲明skip2爲256×(mlen-1)數組，另一方面，您將其填充爲(mlen+1)×256數組。

下一個循環，

for(i = mlen-2;i>=1;i--) { 
    for(j=ready[pattern[i]]-1;j>=max(i,mlen-k);j--) 
     skip2[j][pattern[i]] = j-i; 
    ready[pattern[i]] = max(i,mlen-k); 
}

您使用ready[pattern[i]]已設置之前。我不知道這些錯誤是否是導致失敗的測試用例的原因，但它們很容易想像。

來源

2012-03-08 18:56:06

如果丹尼爾的建議不能解決問題，這裏有一對夫婦更多的東西，看起來很奇怪：

return j-1; // I would expect "return j;" here

這似乎很奇怪，如果你有K = 0，MLEN = 1，則最高值j可以取tlen + k-1，所以最高返回值是tlen-2。在匹配模式「A」對一個字符串「A」不會在位置0

另一個怪胎返回匹配換句話說就是循環：

for(i = mlen-2;i>=1;i--) // I would expect "for(i = mlen-2;i>=0;i--)" here

似乎奇怪的是，在預處理你會從不訪問模式中的第一個字符（即不讀取模式[0]）。

來源

2012-03-08 19:57:12

Boyer Moore k-不匹配算法失敗

回答

相關問題