KMP文字列検索アルゴリズムの最悪のケースは何ですか？

誰も私に最悪のケース "テキスト文字列 - パターンのペア" KMPアルゴリズムの実装をテストすることを提案できますか？KMP文字列検索アルゴリズムの最悪のケースは何ですか？

2011-10-20 Mustafa Zengin

ですKMPは線形のランタイムの複雑さを持っているため、最後にターゲットを持つ文字列は最悪の場合に実行されます。あなたの実装は多項式であり、すべての場合が線形時間で実行されます。 – davin

Knuth、Morris、Prattは、アルゴリズムの最悪のケースが $ \ phi_1 = bと定義されているフィボナッチ文字列であることを証明しています。彼らの論文では、 \ phi_2 = b、\ phi_n = \ phi_ {n-1} \ phi_ {n-2} $セクションを確認してください。5.論文の理論的考察。 –

役に立てば幸い、それはまだO(m+n)

出典

2011-10-20 16:48:50

'O（n + m）' – davin

@davin right、corrected –

不一致が発生するたびに接頭辞 - 接尾辞照合テーブルに従ってパターン文字ポインタを左にシフトします。答えの例では、すべてのy文字が一致していないと判断し、パターン1の文字ポインタを一度に左にシフトし続けます。テキストにc1のx文字とc2のy文字がない場合、比較の合計数は（c1 + c2 *パターンサイズ）になります。私は正しい？ –

あなたはここにKMPアルゴリズム上で何かを見つけることができます。

KMP ALGORITHM

クイックエキス：

クヌース、モリスとプラットは、以下のことにより、第1の線形時間文字列マッチングアルゴリズムを発見ナイーブなアルゴリズムの緊密な分析 Knuth-Morris-Prattアルゴリズムは、テキストのスキャン中にナイーブなアプローチが浪費されたという情報を保持します。情報のこの無駄を回避することにより、最悪の場合にはという最適なO（n + m）の実行時間を達成します。 最悪の場合、Knuth-Morris-Pratt アルゴリズムでは、テキスト内のすべての文字と少なくともパターンを調べなければなりません。

アルゴリズムについて理解しているものを鎮静化し、必要なものを見つけることができます。

は私が

xx........x 
| n times |

ようなパターンと

xxx.........xyx...........xy.... 
| n-1 times | | n-1 times |

のような文字列は、最悪のケースの一つだろうと言うでしょう、それは

出典

2011-10-20 16:47:36

KMP文字列検索アルゴリズムの最悪のケースは何ですか？

答えて

関連する問題