KMPに関する多くの記事では、KMP自体の障害関数には多数のアプリケーションがあると述べています。
そのようなアプリケーションの1つは、k回連結すると元の文字列（ピリオド）を与える最小の文字列を見つけることです。
しかし、私は他のものを見つけることができませんでした。KMP障害機能に関連する他の問題は何ですか？
1 に答える
3
KMPは、文字列のすべてのプレフィックスの境界を計算します。これ自体が、文字列のアルゴリズムの重要な概念です。（単語全体の境界を計算すること自体は簡単ではなく、KMP（失敗関数）がそれを行うための標準です！）
sの境界線は、sの接頭辞と接尾辞の両方である単語です。
お気づきのとおり、境界を計算する機能の優れたアプリケーションは、特定の文字列sに対していくつかの自然なk w ^ k= sとなるような最小の文字列wを計算する可能性です。これはsの原始根と呼ばれます。
この理由は、文字列の境界線とピリオドの間の二重性です。文字列sのピリオドは、 sが文字列wwwwのプレフィックスであるようなs以下の任意の文字列wです...たとえば、abcはabcabcabのピリオドです。単語の境界線とピリオドの間には1：1の対応があることがわかります。上記の例では、 abcabはabcabcabの境界であることに注意してください。一般に、wがsの期間である場合は常に、wを削除した後にsから残る文字列最初から（w ^ -1 s）はsの境界です。同様に、wがsの境界である場合、接尾辞wを削除したときにsから残る単語はsのピリオドです。
ピリオドは、文字列のプロパティを分析する上で重要なツールです。これらは、たとえば、文字列の繰り返し（実行）を見つけるためのアルゴリズムで使用されます。概要については、このペーパーを参照してください。
于 2012-08-14T05:24:33.717 に答える