5

Aho-Corasick と 1 次元 KMP の組み合わせを使用して 2 次元探索の問題を解決しようとしましたが、まだ高速化が必要です。

詳しく説明すると、サイズ n1*n2 の文字の行列 A があり、サイズ m1*m2 の小さい行列 B のすべての出現箇所を見つけたいと考えています。可能。

例えば：

A = a b c b c b
    b c a c a c
    d a b a b a
    q a s d q a

と

B = b c b
    c a c
    a b a

アルゴリズムは、たとえば一致の左上隅のインデックスを返す必要があります。この場合、(0,1) と (0,3) を返す必要があります。オカレンスが重複する可能性があることに注意してください。

4

1 に答える 1

4

私が最近見つけたBaker-Bird アルゴリズムと呼ばれるアルゴリズムは、KMP を 2 次元に部分的に一般化したものと思われます。Aho-Corasick アルゴリズム(それ自体が KMP の一般化) と KMP アルゴリズムの2 つのアルゴリズムをサブルーチンとして使用して、2 次元グリッドでパターンを効率的に検索します。

これがあなたが探しているものかどうかはわかりませんが、うまくいけば役に立ちます！

于 2012-02-16T05:12:42.177 に答える