2
Knuth-Morris-Prattアルゴリズムを複数回検索するためにO（n）時間の複雑さを実行することはできますか？複数のoccurencesのKMPアルゴリズム
A
答えて
2
文字列S [0、...、N]があるとします。接頭辞配列のi番目のエントリは、接尾辞に一致するS [0、...、i]の最大接頭辞の長さを格納することを思い出してください。 $ subjectというパターンのプレフィックス配列Pを計算することができます（$がsubjectにないと仮定します）。 P [i] == length（パターン）のようなインデックスを見つけることは、線形時間で行うことができます。
+0
非常にきれいな解決策、ありがとうございます。 –
関連する問題
- 1. KMPアルゴリズムのプレフィックステーブル
- 2. KMPパターン検索アルゴリズム
- 3. Pythonを使用したKMPアルゴリズム
- 4. KMPの失敗関数
- 5. DMP構築の過程をKMPアルゴリズムで理解する方法
- 6. いつKMPアルゴリズムを使うのが良いですか？
- 7. KMP文字列検索のアルゴリズムですか？
- 8. KMPアルゴリズムのジャンプがエラーを起こしやすいですか？
- 9. KMPアルゴリズムが複数回バックトラックする必要がある場合の例を構築する
- 10. テスト複数のアルゴリズム
- 11. INDEX MATCH multiple occurences
- 12. PySpark count common occurences
- 13. KMPアルゴリズムアプリケーション
- 14. KMP文字列検索アルゴリズムの最悪のケースは何ですか？
- 15. Pandas、Python：df行サブセクションのcount occurences
- 16. この関数のアルゴリズムの複雑さ
- 17. クラス/アルゴリズムの複数のバージョンのデザインパターン
- 18. KMPの失敗機能
- 19. KMPアルゴリズムは単純化されたBoyer-Mooreアルゴリズムと比較してパフォーマンスが低下しますか？
- 20. 検索アルゴリズム階層と複数のフィルタ
- 21. 関数の複雑さとアルゴリズム
- 22. Occurencesにカウントを続ける
- 23. VBA Excelのカウント同じシート名Occurences
- 24. 複数のoccurencesを持つより大きなものから特定の小さな文字列を取得
- 25. アルゴリズムの複雑さ
- 26. KMP計算プレフィックス関数の結果を表示
- 27. 複数の引数にfor_eachなどのSTLアルゴリズムを適用
- 28. 複合関数で計算されたアルゴリズムの複雑度
- 29. このパターン検出方法は、KMPまたはZアルゴリズム実装よりも優れていますか？
- 30. 数学演算のアルゴリズムのアルゴリズム
あなたはKMPアルゴリズムを実行して、O（Kn）= O（n）でこれらのKの異なる単語の出現を見つけることができます –