問題タブ [knuth-morris-pratt]

Knuth-Morris-Pratt、Rabin-Karp などのほかに、利用可能な文字列マッチング アルゴリズムは何ですか?

KMP ( Knuth–Morris–Pratt ) が 1 次元検索に使用されることは知っています。2次元配列のデータに適用できますか? それとももっと高度なものがありますか？

KMPパターンマッチングアルゴリズムの理論的根拠は何ですか？

アルゴリズム自体は理解していますが、クヌース、モリス、プラットがこのアルゴリズムをどのように発明したのかわかりません。

数学的な証明はありましたか？

リンクをお願いします。

また、別の文字列のすべての出現を見つけるために、どのアルゴリズムが最悪の場合の複雑さを持っているかを知りたいです。Boyer–Moore のアルゴリズムには線形時間の複雑さがあるようです。

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

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

例えば：

と

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

与えられたパターンのプレフィックス関数にこのようなものがある可能性はありますか？

0 0 1 2 3 0 1 2 3 4 5 3 4 56 7 0 1 2

上記の45の後のプレフィックス関数では、6または0の可能性しかありませんか？上記のように45の後に3（5未満で0より大きい）などの可能性がある場合、パターンはどのようになりますか。

これに似たパターンしか考えられませんが、

ありがとう。

一致する文字列とパターンが与えられた場合、0または1つの不一致がある一致をどれだけ効率的に見つけることができますか。

KMPアルゴリズムを変更しようとしましたが、アプローチがわかりません。

問題を進めるためのアイデアを教えてください。

ありがとう。

文字列bに文字列（aとしましょう）が何回出現するかを検索したいと思います。Knuth-Morris-Pratt Algorithm を実装することを考えましたが、組み込みの Java 関数を好みます。このような機能はありますか？私は何度も使用するので、できるだけ複雑度が低い関数にしたいと考えています。

次のKMP実装があります：

ここでテストできます：http：//liveworkspace.org/code/d2e7b3be72083c72ed768720f4716f80

それは小さな文字列でうまく機能します、そして私はそれを大きなループでテストしました、この方法ですべてがうまくいきます。

しかし、検索している部分文字列と完全な文字列を次のように変更すると、次のようになります。

最初の試行の後、この実装は失敗します...

アルゴリズムを文字列内のそのようなデータで機能させるために、KMPの実装を修復するのを手伝っていただけませんか...

私はこれに関するほとんどの文献を読んで最善を尽くしましたが、KMP アルゴリズムで使用される失敗関数がどのように構築されるかについてはまだ何も理解していません。私は主にhttp://community.topcoder.com/tc?module=Static&d1=tutorials&d2=string検索チュートリアルを参照してきましたが、これはほとんどの人が優れていると考えています。しかし、私はまだそれを理解していません。お手数をおかけしますが、もう少し分かりやすくご説明いただけますと幸いです。