5

KMPに関する多くの記事では、KMP自体の障害関数には多数のアプリケーションがあると述べています。

そのようなアプリケーションの1つは、k回連結すると元の文字列(ピリオド)を与える最小の文字列を見つけることです。

しかし、私は他のものを見つけることができませんでした。KMP障害機能に関連する他の問題は何ですか?

4

1 に答える 1

3

KMPは、文字列のすべてのプレフィックスの境界を計算します。これ自体が、文字列のアルゴリズムの重要な概念です。(単語全体の境界を計算すること自体は簡単ではなく、KMP(失敗関数)がそれを行うための標準です!)

sの境界線は、sの接頭辞と接尾辞の両方である単語です。

お気づきのとおり、境界を計算する機能の優れたアプリケーションは、特定の文字列sに対していくつかの自然なk w ^ k= sとなるような最小の文字列wを計算する可能性です。これはsの原始根と呼ばれます。

この理由は、文字列の境界線とピリオドの間の二重性です。文字列sのピリオドは、 sが文字列wwwwのプレフィックスであるようなs以下の任意の文字列wです...たとえば、abcabcabcabのピリオドです。単語の境界線とピリオドの間には1:1の対応があることがわかります。上記の例では、 abcabはabcabcabの境界であることに注意してください。一般に、wがsの期間である場合は常に、w削除た後にsから残る文字列最初から(w ^ -1 s)はsの境界です。同様に、wがsの境界である場合、接尾辞wを削除したときにsから残る単語はsのピリオドです。

ピリオドは、文字列のプロパティを分析する上で重要なツールです。これらは、たとえば、文字列の繰り返し(実行)を見つけるためのアルゴリズムで使用されます。概要については、このペーパーを参照してください。

于 2012-08-14T05:24:33.717 に答える