Knuth-Morris と Pratt は、文字列マッチング問題に対する線形時間アルゴリズムを導入しました。マッチング時間 O (n) は、マッチング対象のパターン 'p' の一部の要素との比較に以前に関与していた 'S' の要素との比較を回避することによって達成されます。つまり、文字列「S」に対するバックトラックは決して発生しません。
KMP アルゴリズムのコンポーネント:
1. 接頭辞関数 (Π): パターンの接頭辞関数 Π は、パターンがそれ自体のシフトに対してどのように一致するかに関する知識をカプセル化します。この情報は、パターン「p」の無駄なシフトを避けるために使用できます。つまり、これにより、文字列「S」のバックトラックを回避できます。
2. KMP マッチ: 文字列 'S'、パターン 'p'、およびプレフィックス関数 'Π' を入力として使用して、'S' 内の 'p' の出現を検索し、その後出現が検出されるまでの 'p' のシフト数を返します。
接頭辞関数 (Π)
次の疑似コードは、接頭辞関数 Π を計算します。
<strong>COMPUTE- PREFIX- FUNCTION (P)</strong> 1. m ←length [P] //'p' pattern to be matched 2. Π [1] ← 0 3. k ← 0 4. for q ← 2 to m 5. do while k > 0 and P [k + 1] ≠ P [q] 6. do k ← Π [k] 7. If P [k + 1] = P [q] 8. then k← k + 1 9. Π [q] ← k 10. Return Π
実行時間分析:
プレフィックス関数を計算するための上記の疑似コードでは、ステップ 4 からステップ 10 までの for ループが「m」回実行されます。 Step1からStep3までは一定の時間がかかります。したがって、プレフィックス関数の計算の実行時間は O (m) です。
例： 以下のパターン 'p' の Π を計算します。
エフムービーズ
解決：
Initially: m = length [p] = 7 Π [1] = 0 k = 0
6 回反復した後、プレフィックス関数の計算が完了します。
KMP は以下と一致します。
パターン 'p'、文字列 'S'、およびプレフィックス関数 'Π' を入力として持つ KMP マッチャーは、S 内の p の一致を見つけます。次の疑似コードは、KMP アルゴリズムの一致するコンポーネントを計算します。
<strong>KMP-MATCHER (T, P)</strong> 1. n ← length [T] 2. m ← length [P] 3. Π← COMPUTE-PREFIX-FUNCTION (P) 4. q ← 0 // numbers of characters matched 5. for i ← 1 to n // scan S from left to right 6. do while q > 0 and P [q + 1] ≠ T [i] 7. do q ← Π [q] // next character does not match 8. If P [q + 1] = T [i] 9. then q ← q + 1 // next character matches 10. If q = m // is all of p matched? 11. then print 'Pattern occurs with shift' i - m 12. q ← Π [q] // look for the next match
実行時間分析:
ステップ 5 で始まる for ループは「n」回、つまり文字列「S」の長さだけ実行されます。ステップ 1 からステップ 4 までは一定の時間がかかるため、ループの実行時間はこれによって支配されます。したがって、マッチング関数の実行時間は O (n) です。
例： 次のように文字列「T」とパターン「P」を指定すると、次のようになります。
KMP アルゴリズムを実行して、「T」に「P」が出現するかどうかを調べてみましょう。
「p」の場合は接頭辞関数、?は以前に計算されており、次のようになります。
解決：
Initially: n = size of T = 15 m = size of P = 7
パターン 'P' は文字列 'T' で複雑になることが判明しました。一致が見つかるまでに行われたシフトの総数は、i-m = 13 - 7 = 6 シフトです。