c++ - 加快 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]];
    }
}

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

我想知道我在哪里/做错了什么（我真的不想要代码）。

编辑：由于评论

您知道如何在不实现完整的 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]];

根据不需要存在的字符跳过（如果模式结尾与文本结尾对齐）。