string - Knuth-Morris-Prattアルゴリズムでのパターンプレフィックス関数の計算

Question

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

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より大きい）などの可能性がある場合、パターンはどのようになりますか。

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

a b a b a b a b c a 
0 0 1 2 3 4 5 6 0 1

ありがとう。

Answer 1

これは、6の後にリンク4が失敗するパターンの例です。

a b c a b c d a b c a b c a
0 0 0 1 2 3 0 1 2 3 4 5 6 4

Answer 2

あなたの特定の例は不可能です。目的のプレフィックステーブルから文字列の作成を開始すると、次のようになります。

0 0 1 2 3 0 1 2 3 4 5 3 4 5 6 7 0 1 2
a b a b a c a b a b a

1. 任意の最初の記号、たとえば
2. 2番目の記号は最初の記号とは異なる必要があります。そうでない場合、プレフィックスの長さは1になります。
3. 3番目は最初と同じでなければなりません
4. 4番目は2番目と同じでなければなりません
5. 5番目は3番目と同じでなければなりません
6. これまでに使用された2つの記号のどちらでもない場合、aはプレフィックス長1、bは4になります。
7. 7番目は最初でなければなりません
8. 2番目でなければなりません
9. 3番目でなければなりません
10. 4番目でなければなりません
11. 5番目でなければなりません
12. aはプレフィックス長1を与え、bは4を与え、cは6を与え、他のすべては0を与えます

長さの接頭辞に対応するテーブルのエントリは、その接頭辞pの最も広い境界線の幅を示しbますw。次のエントリは、 w+1（拡張可能な場合b）、0（一致するプレフィックスがない場合）、またはの境界線の幅より1つ大きい場合にのみ指定できbます。

したがって、length-pプレフィックス（と）table[p]の最も広い境界線の幅が含まれている場合は、、、...、のいずれかになります。table[0] = -1table[p+1]1+table[p]1+table[table[p]]1+table[table[...[table[p]]]] = 1 + table[0] = 0