Алгоритм k-несоответствия Бойера Мура не работает - PullRequest
Новая
       20

Алгоритм k-несоответствия Бойера Мура не работает

0 голосов
/ 08 марта 2012

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

Ответы [ 2 ]

2 голосов
/ 08 марта 2012

Вы неправильно инициализируете свои массивы, 

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

1 голос
/ 08 марта 2012

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

    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] не читается).

...