Ошибка алгоритма k-несоответствий Boyer Moore

Question

Я проделал программу для сравнения строк с одним несоответствием на веб-сайте программирования. Это дает мне неправильный ответ. Я много работал над этим, но я не мог найти тестовые теги, где мой код терпит неудачу. Может ли кто-нибудь предоставить мне тестовые примеры, когда мой код не работает. Я сделал сравнение с помощью Бойер Мур Horspool алгоритм 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; 
} 

Answer 1

Вы не Инициирование ваши массивы правильно,

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]] до того, как было установлено. Я не знаю, являются ли эти ошибки причиной неудачного теста, но это легко представить, что они делают.

Answer 2

Если предложения Даниила не решают проблему, вот несколько вещей, которые выглядят странно:

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

Это кажется странным, как если у вас есть к = 0, mlen = 1, то самое высокое значение, j может принимать tlen + k-1, и поэтому самым высоким возвращаемым значением является tlen-2. Другими словами, соответствующих шаблону «а» против строки «а» не будет возвращать матч на позиции 0.

Другая причуда петля:

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

кажется странным, что в предварительной обработки вы будете никогда не получите доступ к первому символу в вашем шаблоне (т. е. шаблон [0] не читается).