加速实现Boyer-Moore-Horspool字符串搜索

Question

我在c++中实现BMH算法时遇到了一点麻烦。

代码如下:

#define Nm 2000005
int D[256];
char To[Nm],P[Nm],*T;
int Tl,Pl;
int cont;
void initialize_Lenght()
{
    Tl=strlen(To);
    Pl=strlen(P);
    T=To;
}
void compute_D()
{
    for(int i=0;i<256;i++)
        D[i]=Pl;
    for(int i=0;i<Pl;i++)
        D[P[i]]=Pl-i;
}
void Boyer_Moore()
{
    int i;
    while ( Tl>=Pl )    
    {
        for(i=Pl-1;T[i]==P[i]&&i>=0;i--)
            if(i==0)
            {
                if(cont<1000)
                    v[cont]=(T-To); // I also have to store the first 1000 values 
                cont++;
            }
            Tl -= D[T[i+1]];
            T += D[T[i+1]];
    }
}

它适用于大多数示例，但也有一些示例不起作用(到目前为止，我发现只有从不同来源下载的大型测试)。

我想知道我做错了什么(我真的不想要代码)。

Edit:由于注释

你知道我怎样才能使这个算法运行得更快而不实现它的一个完整的Boyer-Moore版本吗?

Answer 1

中测试的顺序

for(i=Pl-1;T[i]==P[i]&&i>=0;i--)

是错误的。在完全匹配之后，比较T[-1]和P[-1]，然后检查索引是否允许。

如果最后一个模式字符不匹配，

Tl -= D[T[i+1]];
T += D[T[i+1]];

根据不需要存在的字符跳过(如果模式结束与文本结束对齐)。