0

プログラミングのWebサイトで、1つの不一致がある文字列を比較するためのプログラムを実行しました。それは私に間違った答えを与えます。私はこれに広範囲に取り組んできましたが、コードが失敗するテストケースを見つけることができませんでした。誰かが私のコードが失敗したテストケースを教えてもらえますか？最速の検索アルゴリズムであるBoyerMooreHorspoolk-mismatchesアルゴリズムを使用して比較を行いました

コードはそれ自体です

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;
}
4

2 に答える 2

2

アレイを正しく初期化していない、

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-08T18:56:06.500 に答える
1

ダニエルの提案で問題が解決しない場合は、奇妙に見えることがいくつかあります。

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

これは、k = 0、mlen = 1であるかのように奇妙に思えます。その場合、jが取ることができる最大値はtlen + k-1であるため、最大の戻り値はtlen-2です。言い換えると、パターン'a'を文字列'a'と照合しても、位置0では一致が返されません。

もう1つの奇妙な点は、ループです。

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

前処理でパターンの最初の文字にアクセスしない（つまり、pattern [0]が読み取られない）のは奇妙に思えます。

于 2012-03-08T19:57:12.337 に答える