0

我已经在编程网站上完成了一个与一个不匹配的字符串比较的程序。它给了我错误的答案。我已经广泛地研究它，但是我找不到我的代码失败的测试用例。有人可以提供我的代码失败的测试用例吗？我已经使用 Boyer Moore Horspool k-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

You aren't initialising your arrays correctly,

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

On the one hand, you declare skip2 as a 256×(mlen-1) array, on the other hand, you fill it as a (mlen+1)×256 array.

In the next loop,

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

you use ready[pattern[i]] before it has been set. I don't know if those mistakes are what's causing the failing testcase, but it's easily imaginable that they do.

于 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 处返回匹配项。

另一个奇怪的是循环：

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

奇怪的是，在预处理中您永远不会访问模式中的第一个字符（即未读取模式 [0]）。

于 2012-03-08T19:57:12.337 回答