Rabin-Karpを使用して文字列内の複数のパターンを検索する

Question

Rabin-Karp文字列照合アルゴリズムのwikipedia entryによれば、線形の複雑さを維持しながら文字列内の複数のパターンを同時に探すことができます。これは、すべてのパターンが同じ長さであれば簡単に行うことができますが、異なる長さのパターンを同時に検索するときにO（n）の複雑さをどのように保つことができるかはまだわかりません。誰かがこれにいくつかの光を発することができますか？

編集（2011年12月）：

Wikipediaの記事は、以来、更新され、もはやO（n）の中に長さの異なる複数のパターンに一致するように主張してきました。

Answer 1

私はとにかくこれが正解であるかどうかわからないんだけど、：ハッシュ値を構築しながら

、我々は文字列のハッシュのセットで一致を確認することができます。別名、現在ハッシュ値。ハッシュ関数/コードは通常ループとして実装され、そのループの中にクイックルックアップを挿入することができます。

もちろん、mを選択して、文字列のセットから最大の文字列長を取得する必要があります。

更新：ウィキペディアから、

[...] 
for i from 1 to n-m+1 
     if hs ∈ hsubs 
      if s[i..i+m-1] = a substring with hash hs 
       return i 
     hs := hash(s[i+1..i+m]) // <---- calculating current hash 
[...] 

我々はmステップで現在ハッシュを計算します。各ステップには、一時的なというハッシュ値があり、ハッシュのセットの中で（O（1）複雑さを）調べることができます。すべてのハッシュは同じサイズ、つまり32ビットを持ちます。

アップデート2：償却（平均）O（N）時間複雑？

私はmが最大文字列長を持たなければならないと言った。私たちは反対のものを利用することができます。
hashing for shifting substring searchと固定されたmサイズでは、O（n）の複雑さを達成できます。

可変長の文字列がある場合、mを最小文字列長に設定できます。さらに、ハッシュのセットでは、ハッシュを文字列全体と関連付けるのではなく、ハッシュの最初のm文字と関連付けます。
現在、テキストを検索している間、現在のハッシュがハッシュセットに含まれているかどうかをチェックし、一致する文字列を調べます。

この手法では誤警報が増加しますが、平均してO（n）時間の複雑さがあります。

Answer 2

これは、部分文字列のハッシュ値が数学的に関連しているからです。ハッシュH（S、j）は（ストリングSのj番目の位置から始まる文字のハッシュ）を計算すると、長さメートルの列にO（M）時間を要します。 （S、j + 1）H（S、j） H（S、j）の関数として表現することができるので、一定の時間内に実行することができます。 。O（m）+ O（m）、すなわち線形時間である。これは、より詳細に記載されている

Here's a link（「ラビン - カープが速くなりますか？」などの項を参照）