-1

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 の完全なバージョンを実装せずに、このアルゴリズムをより高速に実行する方法を知っていますか?

4

1 に答える 1

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

存在する必要のない文字に従ってスキップします (パターンの末尾がテキストの末尾に揃えられている場合)。

于 2013-01-16T20:39:47.317 に答える