これでマスター！KMPアルゴリズムの理論と実装

By /

これでマスター！KMPアルゴリズムの理論と実装を徹底解説

序章：文字列検索の世界とKMPアルゴリズムの輝き

コンピュータの世界では、文字の並びである「文字列」が重要な役割を果たしています。あなたが今読んでいるこの文章も、Webサイトのコンテンツも、プログラムのソースコードも、データベースに格納された情報も、すべて文字列として扱われます。そして、これらの膨大な文字列の中から、特定のパターンを持つ文字列を見つけ出す操作、すなわち「文字列検索（Pattern Matching）」は、コンピュータサイエンスの基本的な操作の一つです。

テキストエディタで特定の単語を検索したり、Webブラウザでキーワードを入力して情報を探し出したり、あるいはより高度なレベルでは、ゲノム配列の中から特定のDNAパターンを発見したり、ネットワーク通信における特定のパケットシグネチャを検出したりと、文字列検索は私たちのデジタルライフのあらゆる場面で利用されています。

この文字列検索を行うアルゴリズムは数多く存在しますが、その中でも理論的に美しく、かつ実用的にも非常に効率が良いとされるのが「KMPアルゴリズム」です。KMPは、その発明者であるDonald Knuth、Vaughan Pratt、およびJames H. Morrisの3人の頭文字を取って名付けられました。彼らがこのアルゴリズムを発表したのは1977年のことですが、その革新的なアイデアは今日に至るまで文字列検索の分野で重要な位置を占め続けています。

しかし、KMPアルゴリズムは、その効率性や美しさとは裏腹に、初めて学ぶ人にとっては少し難解に感じられるかもしれません。特に、アルゴリズムの核となる「失敗関数（Failure Function）」あるいは「部分文字列テーブル（Prefix Function）」と呼ばれる補助的なテーブルの概念や構築方法、そしてそれが検索プロセスにどのように利用されるのかが理解の壁となりやすいポイントです。

本記事では、KMPアルゴリズムを「マスターする」ことを目標に、その理論的な背景から具体的な実装方法までを、初心者の方にも理解できるよう、可能な限り詳細かつ丁寧に解説していきます。まずは、KMPアルゴリズムがなぜ必要とされるのかを理解するために、最もシンプルで直感的な文字列検索アルゴリズムを見てみましょう。

1. ナイーブな文字列検索アルゴリズム：シンプルゆえの限界

最も直感的で理解しやすい文字列検索アルゴリズムは、「ナイーブ法（Naive Method）」あるいは「総当たり法」と呼ばれるものです。この方法は、検索対象のテキスト（以下 T とします）の先頭から順に、検索したいパターン（以下 P とします）と比較していくという、非常に単純なものです。

ナイーブ法の動作原理

  1. テキスト T の先頭（インデックス 0）からパターン P との比較を開始します。
  2. テキスト中の現在の位置から、パターン P の長さと同じだけ文字を取り出し、パターン P の各文字と順番に比較していきます。
  3. 比較が一致した場合、パターンが見つかったとしてその開始位置を報告します。
  4. 比較中に一つでも文字が不一致だった場合、パターン P をテキスト T の次の位置（開始位置を1つずらす）に移動させ、再度ステップ2からの比較を行います。
  5. この操作を、テキスト T の最後までパターンをずらしながら繰り返します。パターンがテキストの範囲を超えるまでに見つからなければ、パターンは存在しなかったと判断します。

具体例

テキスト T = ABABDABACDABABCABAB
パターン P = ABABCABAB

  1. T[0]から比較: ABABDABACDABABCABAB vs ABABCABAB -> T[0…8] と P[0…8] を比較

    • T[0]==P[0] (A==A) -> 一致
    • T[1]==P[1] (B==B) -> 一致
    • T[2]==P[2] (A==A) -> 一致
    • T[3]==P[3] (B==B) -> 一致
    • T[4]==P[4] (D==C) -> 不一致！
      比較失敗。T[0]から開始した比較は失敗しました。

  2. パターンを1つずらし、T[1]から比較: ABABDABACDABABCABAB vs ABABCABAB -> T[1…9] と P[0…8] を比較

    • T[1]==P[0] (B==A) -> 不一致！
      比較失敗。T[1]から開始した比較も失敗しました。

  3. パターンを1つずらし、T[2]から比較: ABABDABACDABABCABAB vs ABABCABAB -> T[2…10] と P[0…8] を比較

    • T[2]==P[0] (A==A) -> 一致
    • T[3]==P[1] (B==B) -> 一致
    • …
    • T[8]==P[6] (C==B) -> 不一致！
      比較失敗。T[2]から開始した比較も失敗しました。

…というように、不一致が起こるたびにパターンをわずか1文字だけずらして、また最初から比較を繰り返します。

計算量と非効率性

ナイーブ法の計算量を考えてみましょう。テキスト T の長さを n、パターン P の長さを m とします。最悪の場合、テキスト T のほぼすべての位置から比較を開始する必要があり、それぞれの位置での比較には最大で m 回の文字比較が必要です。例えば、テキスト T = AAAA...AAAB (Aが n-1個、最後にB) に対して、パターン P = AAAA...AAB (Aが m-1個、最後にB) を検索する場合を考えます。テキストの各位置で、最後の文字以外はパターンと一致しますが、最後の1文字で必ず不一致が発生します。このとき、テキストの各位置 i (0 ≤ i ≤ n-m) からの比較で m 回近くの文字比較が必要になります。したがって、全体の計算量は O((n-m+1) * m) となり、おおよそ O(nm) となります。

これは、nやmが非常に大きくなった場合に深刻な問題となります。特に、先ほどの例のようにパターンとテキストがよく似ている場合（ほとんど一致して、最後で不一致になる場合）に、多くの文字比較が無駄に繰り返されてしまいます。

ナイーブ法の最大の非効率性は、比較が失敗したときに、テキストポインタをほとんど戻し、パターンの比較位置も最初に戻してしまう点にあります。すでに一致が確認された部分の情報が、パターンのずらし方や次の比較位置の決定に全く活用されていません。KMPアルゴリズムは、この点の改善に焦点を当てたアルゴリズムです。

2. KMPアルゴリズムの核心：無駄な比較をなくすには？

KMPアルゴリズムは、ナイーブ法の非効率性を克服するために、以下の重要なアイデアに基づいています。

アイデア1：比較失敗時にテキストポインタを戻さない

ナイーブ法では、比較が失敗するとテキストポインタを戻してパターンの開始位置をずらします。KMPでは、テキストのポインタは常に前方（またはその場に留まる）に進みます。一度比較したテキスト中の文字は、再び比較する必要がないようにします。

アイデア2：過去の比較結果をパターンのずらし方に活用する

比較中に不一致が発生したということは、その直前まではパターンの一部がテキストと一致していたということです。KMPアルゴリズムは、この「一致していた部分」に関する情報を最大限に活用し、次にパターンをテキストのどの位置に置いて比較を再開すれば良いかを賢く判断します。

具体的には、パターン P とテキスト T を比較していて、パターン P の j 番目の文字 (P[j]) とテキスト T の i 番目の文字 (T[i]) が不一致だったとします。その直前まで、パターン P の 0 から j-1 までの部分 (P[0…j-1]) が、テキスト T の i-j から i-1 までの部分 (T[i-j…i-1]) と完全に一致していました。

図で示すと、以下のようになります。

テキスト T: ... T[i-j] ... T[i-1] T[i] ...
パターン P: ... P[0] ... P[j-1] P[j] ...
^--- 一致していた部分 ---^
^--- 不一致 T[i] != P[j] ---^

この不一致が起こった後、次にパターンをどこにずらせば、無駄な比較を避けつつパターンを見つけられる可能性があるでしょうか？ パターンをずらした後、そのずらしたパターンの先頭部分が、テキストの T[i-j…i-1] のどこかと一致している必要があります。もし一致していなければ、T[i-j…i-1] の部分にパターン P の先頭部分が現れることはありえないからです。

そこで KMP は考えます。「パターン P の先頭部分が、一致していたテキスト部分 T[i-j…i-1] の中に、どこまで含まれている可能性があるか？」
そして、一致していたテキスト部分 T[i-j…i-1] は、パターン P の部分 P[0…j-1] と同じです。
したがって、KMPが知りたいのは、「パターン P の部分 P[0…j-1] の中で、その『接尾辞』が、パターン P の『接頭辞』として現れる最も長い部分」です。

言葉だけでは分かりにくいので、例で考えてみましょう。
パターン P = ABABABC を検索している途中で、P[6] (C) とテキスト中の文字が不一致になったとします。そのとき、P[0…5] (ABABAB) はテキストと一致していました。

テキスト T: ... ABABAB ? ... (ここで ? はテキスト中の文字で、パターン P[6]の'C'と不一致)
パターン P: ABABAB C
^------^ 一致していた部分

一致していた部分 ABABAB の中で、「接尾辞」が「接頭辞」として現れる最も長い部分はどこでしょうか？
* 接尾辞 B -> 接頭辞 A と一致しない
* 接尾辞 AB -> 接頭辞 AB と一致する！ (長さ2)
* 接尾辞 BAB -> 接頭辞 ABA と一致しない
* 接尾辞 ABAB -> 接頭辞 ABAB と一致する！ (長さ4)
* 接尾辞 BABAB -> 接頭辞 ABABA と一致しない

最も長い部分は ABAB で、長さは 4 です。
これは何を意味するのでしょうか？ パターン P[0…5] (ABABAB) のうち、後ろから4文字 (ABAB) が、パターン P[0…3] (ABAB) と一致しているということです。

パターン P: ABAB AB
^--^ 接頭辞 (長さ4)
^--^ 接尾辞 (長さ4) - 一致！

つまり、比較が失敗した直前のテキスト中の部分 ABABAB の後ろ4文字 ABAB は、パターン P の先頭4文字 ABAB と同じである、と KMP は知っています。
したがって、次にパターンをずらす際、パターン P の先頭4文字 ABAB を、テキスト中のこの ABAB の位置に合わせてずらせば、その4文字は必ず一致するはずです。そして、その次の文字から比較を再開すれば良いのです。

“`
テキスト T: … [A B A B A B] ? … ([]内は一致していた部分、?は不一致文字)
ナイーブ法: [A B A B A B] C (パターンを1つずらす)
A B A B A B C (先頭から再比較)

KMP法: … [A B A B A B] ? …
A B A B C (一致していた部分の接尾辞と一致する最も長い接頭辞の長さだけずらす)
^–^ -> この部分は必ずテキストと一致する
^———^ -> この部分から比較を再開
“`

この例では、パターン P[0…5] の長さは 6 でした。P[6] で不一致が起こったとき、一致していた部分は P[0…5] です。その中で最も長い「接尾辞かつ接頭辞」の長さは 4 でした。これは、次の比較をパターン P のインデックス 4 から始めれば良いことを意味します。つまり、パターンをずらした後、テキスト中の現在の不一致位置 T[i] に対して、パターン P の P[4] を持ってきて比較を再開するのです。テキストポインタ T[i] はそのまま、パターンポインタ P[j] は新しい開始位置に移動します。

この「パターン P の部分 P[0…j-1] の中で、その『接尾辞』が『接頭辞』として現れる最も長い部分の長さ」を知るための情報を事前に計算しておけば、比較失敗時にパターンをどれだけ賢くずらせるかが分かります。この情報こそが、KMPアルゴリズムの核となる「失敗関数」または「部分文字列テーブル（Prefix Function）」なのです。

3. 部分文字列テーブル（Prefix Function / Failure Function）：KMPの羅針盤

KMPアルゴリズムの効率性の鍵を握るのが、部分文字列テーブル（Prefix Function）です。しばしば pi（π）テーブルとも呼ばれます。このテーブルは、検索対象のテキストではなく、検索パターン P だけに依存して構築されます。したがって、パターン P が変わらない限り、このテーブルを再計算する必要はありません。

piテーブルの定義

パターン P の長さ m に対して、piテーブル pi[0...m-1] は、各インデックス i (0 ≤ i < m) に対して、以下を満たす値 pi[i] を格納します。

pi[i] の値は、パターン P の 0 から i までの接頭辞 P[0…i] において、最も長い真の接頭辞であり、かつ真の接尾辞でもある部分文字列の長さです。

ここで「真の接頭辞」とは、文字列自体を含まない接頭辞のことです（例: “abc” の真の接頭辞は “”, “a”, “ab”）。同様に「真の接尾辞」とは、文字列自体を含まない接尾辞です（例: “abc” の真の接尾辞は “”, “c”, “bc”）。

例えば、パターン P = ABABABC (長さ m=7) に対して pi テーブルを計算してみましょう。

  • pi[0]: P[0] = “A”。真の接頭辞も真の接尾辞も “” (空文字列) のみ。長さは 0。pi[0] = 0。
  • pi[1]: P[0…1] = “AB”。真の接頭辞は “”, “A”。真の接尾辞は “”, “B”。共通する最長は “”。長さは 0。pi[1] = 0。
  • pi[2]: P[0…2] = “ABA”。真の接頭辞: “”, “A”, “AB”。真の接尾辞: “”, “A”, “BA”。共通する最長は “A”。長さは 1。pi[2] = 1。
  • pi[3]: P[0…3] = “ABAB”。真の接頭辞: “”, “A”, “AB”, “ABA”。真の接尾辞: “”, “B”, “AB”, “BAB”。共通する最長は “AB”。長さは 2。pi[3] = 2。
  • pi[4]: P[0…4] = “ABABA”。真の接頭辞: “”, “A”, “AB”, “ABA”, “ABAB”。真の接尾辞: “”, “A”, “BA”, “ABA”, “BABA”。共通する最長は “ABA”。長さは 3。pi[4] = 3。
  • pi[5]: P[0…5] = “ABABAB”。真の接頭辞: “”, “A”, “AB”, “ABA”, “ABAB”, “ABABA”。真の接尾辞: “”, “B”, “AB”, “BAB”, “ABAB”, “BABAB”。共通する最長は “ABAB”。長さは 4。pi[5] = 4。
  • pi[6]: P[0…6] = “ABABABC”。真の接頭辞: “”, “A”, “AB”, …, “ABABAB”。真の接尾辞: “”, “C”, “BC”, …, “BABABC”。共通する最長は “”。長さは 0。pi[6] = 0。

したがって、パターン P = ABABABC の pi テーブルは [0, 0, 1, 2, 3, 4, 0] となります。

piテーブルの値の意味と役割

検索中にパターン P のインデックス j で不一致が発生し、その直前までパターン P の P[0…j-1] がテキストと一致していたとします。このとき、次に比較を再開するパターンのインデックスは pi[j-1] になります。

なぜでしょうか？
不一致が P[j] で起こったということは、テキスト T の T[i-j…i-1] と パターン P の P[0…j-1] が一致していたということです。
pi[j-1] は、パターン P の接頭辞 P[0…j-1] において、最も長い「接頭辞かつ接尾辞」の長さです。
つまり、パターン P の P[0…pi[j-1]-1] という部分文字列は、パターン P の P[j-pi[j-1]…j-1] という部分文字列と全く同じであり、かつこの長さが最も長いということです。

パターン P: P[0] ... P[pi[j-1]-1] ... P[j-pi[j-1]] ... P[j-1] P[j]
^--------------------^--------------------------^
| 接頭辞 (長さ k=pi[j-1]) |
| ^--------------------^
| | 接尾辞 (長さ k=pi[j-1])
| | これは接頭辞 P[0...k-1] と同じ内容

検索中の状態は以下の通りです。
テキスト T: ... T[i-j] ... T[i-pi[j-1]-1] ... T[i-1] T[i] ...
パターン P: P[0] ... P[pi[j-1]-1] ... P[j-pi[j-1]] ... P[j-1] P[j]
^----------------------------------------^ 一致していた部分 (長さ j)
^ 不一致 T[i] != P[j]

一致していた部分 T[i-j…i-1] と P[0…j-1] は同じ文字列です。
P[0…j-1] の「最も長い接頭辞かつ接尾辞」の長さが k = pi[j-1] であるということは、T[i-j…i-1] の後ろ k 文字 (T[i-k…i-1]) が、パターン P の先頭 k 文字 (P[0…k-1]) と同じであるということです。

テキスト T: ... T[i-j] ... T[i-k] ... T[i-1] T[i] ... (k = pi[j-1])
^---------^ この部分がパターンPの先頭k文字P[0...k-1]と同じ
パターン P: P[0] ... P[k-1] ... P[j-k] ... P[j-1] P[j]
^---------^ この部分がテキストT[i-k...i-1]と同じ

したがって、次にパターンをずらす際は、パターン P の P[0…k-1] 部分を、テキスト中の T[i-k…i-1] の位置に合わせれば、その部分は必ず一致します。そして、比較を再開すべき位置は、パターン P のインデックス k = pi[j-1] からとなります。テキスト中の位置は T[i] のままで、パターン中の比較位置が P[j] から P[pi[j-1]] に移動するのです。

もし j=0 のときに不一致が発生した場合（パターン P の先頭文字 P[0] とテキスト T[i] が不一致）、これはパターンをずらしてもテキスト T[i] とパターン P の先頭文字が一致する可能性がないことを意味します（もし一致するなら、それはパターン P の先頭文字しかありえないからです）。この場合、単純にテキストポインタを一つ進めて T[i+1] から、パターン P の先頭 P[0] との比較を再開します。piテーブルは j>0 の場合のずらし方を定義するものですが、j=0 のケースは特殊な初期条件として扱われます。

4. piテーブルの構築アルゴリズム

piテーブルの重要性が分かったところで、次にその構築方法を説明します。テーブル pi は、パターン P の長さ m に依存して O(m) の時間で計算できます。

アルゴリズムの考え方

piテーブル pi[i] は、P[0…i] の中で最も長い「接頭辞かつ接尾辞」の長さです。
私たちは pi[0] から順に pi[m-1] まで計算していきます。
pi[0] は常に 0 です。

インデックス i の pi[i] の値を計算する際に、私たちはすでに pi[0], pi[1], ..., pi[i-1] の値を計算済みであると仮定します。
pi[i] の値は、P[0…i] の「接頭辞かつ接尾辞」の長さ k です。つまり、P[0…k-1] == P[i-k+1…i] を満たす最大の k です。

ここで、pi[i-1] の値を利用します。pi[i-1] は P[0…i-1] の最も長い「接頭辞かつ接尾辞」の長さです。これを k_prev = pi[i-1] とします。これは、P[0…k_prev-1] == P[i-k_prev…i-1] が成り立つことを意味します。

今、P[0…i] の「接頭辞かつ接尾辞」を探しています。もし、P[k_prev] == P[i] であれば、P[0…k_prev-1] == P[i-k_prev…i-1] と P[k_prev] == P[i] を組み合わせると、P[0…k_prev] == P[i-k_prev…i] となります。つまり、P[0…i] において、長さ k_prev + 1 の部分文字列が「接頭辞かつ接尾辞」として存在することになります。この長さ k_prev + 1 が、P[0…i] の最も長い「接頭辞かつ接尾辞」の長さである可能性があります。この場合、pi[i] = k_prev + 1 となります。

もし P[k_prev] != P[i] であれば、長さ k_prev + 1 の「接頭辞かつ接尾辞」は P[0…i] に存在しません。それでは、より短い「接頭辞かつ接尾辞」を探す必要があります。どれだけ短くすれば良いでしょうか？
私たちは P[0…i-1] の中で長さ k_prev = pi[i-1] の「接頭辞かつ接尾辞」が存在することを知っています。もし P[k_prev] != P[i] なら、次に試すべき長さは、この P[0…k_prev-1] という部分文字列（これが P[0…i-1] の最も長い接頭辞かつ接尾辞でした）の中での「最も長い接頭辞かつ接尾辞」の長さになります。これはまさに pi[k_prev-1] です！

“`
P[0] … P[k_prev-1] P[k_prev] … P[i-1] P[i]
^———–^ ^———–^
| 接頭辞 k_prev | 接尾辞 k_prev (これは接頭辞 P[0…k_prev-1] と同じ内容)

もし P[k_prev] != P[i] なら、長さ k_prev+1 の接頭辞/接尾辞は存在しない。
次に試すべきは、P[0…k_prev-1] (これが接尾辞として P[i-k_prev…i-1] に一致していた部分) の中で
最も長い接頭辞かつ接尾辞の長さ。
これは pi[k_prev-1] に他ならない。
新しい候補の長さ k’ = pi[k_prev-1]。
次に P[k’] と P[i] を比較してみる。
“`

したがって、P[k_prev] != P[i] の場合、現在の候補長 k を pi[k_prev-1] に更新し、再度 P[k] と P[i] を比較します。これを、候補長 k が 0 になるまで、または P[k] == P[i] となるまで繰り返します。
もし k が 0 になっても P[0] != P[i] であれば、P[0…i] に長さ 1 以上の「接頭辞かつ接尾辞」は存在しないことになり、pi[i] = 0 となります。もし P[0] == P[i] であれば、長さ 1 の「接頭辞かつ接尾辞」が存在し、pi[i] = 1 となります。

このプロセスを効率的に実現するために、構築中は2つのポインタ（またはインデックス）を使用します。

  • i: piテーブルを計算している現在のインデックス (1 から m-1 まで増加)。これは P[0…i] という接頭辞の末尾のインデックスに対応します。
  • j または k: 現在評価している「接頭辞かつ接尾辞」の長さ。これは同時に、パターン P の接頭辞 P[0…j-1] の末尾インデックス j-1、およびパターン P の接尾辞 P[i-j+1…i] の末尾インデックス i に対応する、次に比較すべきパターン文字のインデックスでもあります。初期値は j = 0 です。

piテーブル構築アルゴリズムの手順

パターン P の長さ m に対して、サイズ m の整数配列 pi を用意します。
pi[0] = 0 とします。
インデックス i を 1 から m-1 まで進めます。
インデックス j を使用し、現在の接頭辞/接尾辞の長さを表します。初期値 j = 0。

  1. i を 1 から m-1 まで繰り返します。
  2. 現在の j の位置の文字 P[j] と、現在の i の位置の文字 P[i] を比較します。
    • while (j > 0 && P[i] != P[j]): もし文字が一致せず、かつ j が 0 より大きい場合（つまり、まだ縮める余地がある場合）、j を pi[j-1] に更新します。これは、「P[0…j-1] の中で、次に短い『接頭辞かつ接尾辞』の長さ」に戻ることを意味します。この操作は、P[i] と一致するパターン P の接頭辞を見つけるまで、または j が 0 になるまで繰り返されます。
    • if (P[i] == P[j]): もし文字が一致した場合、現在の接頭辞/接尾辞の長さ j を1つ増やします (j++)。これは、P[0…j] が P[i-j…i] に一致することが確認できたことを意味します。
    • pi[i] = j: インデックス i に対する pi の値を、更新された j の値とします。

擬似コード

“`
function compute_pi_table(P, m):
pi = array of size m
pi[0] = 0
j = 0 // 長さ (あるいは次に比較するパターンインデックス)

for i from 1 to m-1:
    // P[i] と P[j] を比較する準備
    // もし P[i] と P[j] が一致しない場合、j を pi[j-1] に戻す
    while j > 0 and P[i] != P[j]:
        j = pi[j-1]

    // P[i] と P[j] が一致した場合
    if P[i] == P[j]:
        j = j + 1

    // pi[i] の値を設定 (現在の j は、P[0...i] の最長接頭辞かつ接尾辞の長さ)
    pi[i] = j

return pi

“`

Pythonでの実装例

“`python
def compute_pi_table(pattern):
m = len(pattern)
pi = [0] * m
j = 0 # length of the previous longest prefix suffix

# pi[0] is always 0, start from i = 1
for i in range(1, m):
    # If mismatch after j characters, j becomes pi[j-1]
    # We are essentially looking for the next shortest prefix that is also a suffix
    # in the substring pattern[0...i-1] (or rather, the new potential match length)
    while j > 0 and pattern[i] != pattern[j]:
        j = pi[j-1] # Fall back to the previous prefix-suffix length

    # If characters match, increment the length
    if pattern[i] == pattern[j]:
        j += 1

    # Store the length of the longest prefix-suffix ending at index i
    pi[i] = j

return pi

例の実行

pattern = “ABABABC”
pi_table = compute_pi_table(pattern)
print(f”Pattern: {pattern}”)
print(f”pi table: {pi_table}”)

pattern = “AAAAA”
pi_table = compute_pi_table(pattern)
print(f”Pattern: {pattern}”)
print(f”pi table: {pi_table}”)

pattern = “ABCDE”
pi_table = compute_pi_table(pattern)
print(f”Pattern: {pattern}”)
print(f”pi table: {pi_table}”)

pattern = “ABACABA”
pi_table = compute_pi_table(pattern)
print(f”Pattern: {pattern}”)
print(f”pi table: {pi_table}”)
“`

出力例：
Pattern: ABABABC
pi table: [0, 0, 1, 2, 3, 4, 0]
Pattern: AAAAA
pi table: [0, 1, 2, 3, 4]
Pattern: ABCDE
pi table: [0, 0, 0, 0, 0]
Pattern: ABACABA
pi table: [0, 0, 1, 0, 1, 2, 3]

この構築アルゴリズムの計算量は O(m) です。各ステップ i において、内部の while ループで j の値が減少しますが、j の値は if 条件が満たされた場合に最大1だけ増加します。j の値は i を超えることはありません。j の合計増加量は O(m) であり、j の減少量も合計で O(m) を超えることはありません（j が減少するのは、過去に増加した分を打ち消すため）。したがって、全体の計算量は線形時間 O(m) となります。

5. KMP検索アルゴリズム本体

piテーブルが構築できたら、いよいよそのテーブルを使ってテキスト T の中にパターン P を検索します。

アルゴリズムの考え方

テキスト T のインデックス i とパターン P のインデックス j の2つのポインタを使用します。
i はテキスト T の現在比較中の文字の位置を示します。
j はパターン P の現在比較中の文字の位置を示します。また、同時にパターン P の P[0…j-1] という接頭辞がテキスト T の現在の位置から j 文字分だけ一致していることを示します。

  1. テキスト T の先頭（インデックス 0）から、パターン P の先頭（インデックス 0）との比較を開始します。つまり、i = 0, j = 0 から始めます。

  2. テキスト T の現在の文字 T[i] と、パターン P の現在の文字 P[j] を比較します。

    • if (T[i] == P[j]): もし文字が一致した場合、テキストとパターンの両方のポインタを1つ進めます (i++, j++)。より長い部分での一致を調べ続けるためです。
    • if (j == m): もしパターンポインタ j がパターンの長さに達した場合（つまり j == m）、パターン全体がテキスト中の位置 i-m から一致したことを意味します。これはパターンが見つかったことを示し、位置 i-m を報告します。パターン検索を続ける場合は、次に進む必要があります。ここで、最も重要なKMPのずらしが登場します。パターン全体が見つかったということは、P[0…m-1] が T[i-m…i-1] と一致していたということです。次にパターンをずらして検索を続けるためには、P[0…m-1] の中で「最も長い接頭辞かつ接尾辞」の長さ pi[m-1] を利用します。新しいパターンポインタ j は pi[m-1] となり、テキストポインタ i はそのまま維持されます。これにより、パターン全体が見つかった直後のテキスト位置から、パターンの一部（長さ pi[m-1]）が再び一致しているとみなして、その次の文字から比較を再開できます。
    • else if (i < n && T[i] != P[j]): もし文字が一致せず、かつテキストポインタ i がテキストの範囲内である場合、パターンのずらしが必要です。
      • if (j != 0): もしパターンポインタ j が 0 でない場合（つまり、パターンの先頭文字以外で不一致が起こった場合）、piテーブルを使用してパターンポインタ j を更新します。新しい j の値は pi[j-1] となります。テキストポインタ i はこのとき進めません。これは、現在のテキスト位置 T[i] を、新しいパターン開始位置 P[pi[j-1]] と比較する必要があるためです。先ほどの例で説明したように、pi[j-1] は、一致していた部分 P[0…j-1] の中で、次に一致する可能性がある「接頭辞かつ接尾辞」の長さを教えてくれます。
      • else (j == 0): もしパターンポインタ j が 0 の場合（つまり、パターンの先頭文字 P[0] とテキスト T[i] が不一致だった場合）、これはパターン P の先頭がテキスト T[i] に現れないことを意味します。この場合、単純にテキストポインタ i を1つ進めて T[i+1] とパターン P[0] との比較を再開します。パターンポインタ j は 0 のままです。

  3. テキストポインタ i がテキストの長さに達するか、あるいは発見したすべての位置を報告し終えるまで（発見後に検索を続ける場合）、ステップ2を繰り返します。

擬似コード

“`
function kmp_search(T, n, P, m, pi):
i = 0 // テキストの現在位置 (ポインタ)
j = 0 // パターンの現在位置 (ポインタ)

while i < n:
    // T[i] と P[j] が一致した場合
    if P[j] == T[i]:
        i = i + 1
        j = j + 1

    // パターン全体が一致した場合
    if j == m:
        // パターンがテキスト中の位置 (i - m) で見つかった
        print("Pattern found at index", i - m)

        # 次の出現箇所を探すために、j を pi[j-1] (すなわち pi[m-1]) に戻す
        # テキストポインタ i はそのままで良い
        j = pi[j-1]

    // 一致しない場合 (i < n && P[j] != T[i])
    elif i < n and P[j] != T[i]:
        // もし j が 0 でなければ、pi[j-1] を使って j を戻す
        // テキストポインタ i は進めない
        if j != 0:
            j = pi[j-1]
        // もし j が 0 なら、テキストポインタ i だけを進める
        else:
            i = i + 1

“`

Pythonでの実装例

piテーブル構築関数は既に作成済みとします。

“`python
def kmp_search(text, pattern):
n = len(text)
m = len(pattern)
if m == 0:
print(“Pattern is empty”)
return []
if n == 0:
print(“Text is empty”)
return []

# piテーブルを構築
pi = compute_pi_table(pattern)

occurrences = [] # 見つかった位置を記録するリスト

i = 0  # index for text
j = 0  # index for pattern

while i < n:
    # 文字が一致する場合
    if pattern[j] == text[i]:
        i += 1
        j += 1

    # パターン全体が一致した場合
    if j == m:
        # パターンが見つかった位置を記録
        occurrences.append(i - j)

        # 見つかった後の処理:
        # pi[j-1] (つまり pi[m-1]) を使ってパターンポインタ j を戻す
        # text[i-j...i-1] と pattern[0...m-1] は一致した。
        # pi[m-1] の長さ k は、pattern[0...k-1] == pattern[m-k...m-1] を意味する。
        # これはつまり、text[i-k...i-1] が pattern[0...k-1] と一致しているということ。
        # 次の比較は text[i] と pattern[k] から開始すれば良い。
        # textポインタ i は現在のまま、patternポインタ j を k = pi[m-1] にする。
        j = pi[j-1]

    # 文字が一致しない場合
    elif i < n and pattern[j] != text[i]:
        # j > 0 の場合、pi[j-1] を使ってパターンポインタ j を戻す
        # textポインタ i は進めない（現在の text[i] を、新しい pattern[j] と比較するため）
        if j != 0:
            j = pi[j-1]
        # j == 0 の場合、パターン先頭と text[i] が一致しない
        # textポインタ i を進めて、pattern[0] と text[i+1] を比較
        else:
            i += 1

return occurrences

実行例

text = “ABABDABACDABABCABAB”
pattern = “ABABCABAB”
found_indices = kmp_search(text, pattern)
print(f”Text: {text}”)
print(f”Pattern: {pattern}”)
print(f”Found at indices: {found_indices}”) # 期待される出力: [10]

text = “AAAAABAAAAA”
pattern = “AAAA”
found_indices = kmp_search(text, pattern)
print(f”Text: {text}”)
print(f”Pattern: {pattern}”)
print(f”Found at indices: {found_indices}”) # 期待される出力: [0, 1, 2, 6, 7]
“`

出力例：
Pattern: ABABABC
pi table: [0, 0, 1, 2, 3, 4, 0]
Pattern: AAAAA
pi table: [0, 1, 2, 3, 4]
Pattern: ABCDE
pi table: [0, 0, 0, 0, 0]
Pattern: ABACABA
pi table: [0, 0, 1, 0, 1, 2, 3]
Text: ABABDABACDABABCABAB
Pattern: ABABCABAB
Found at indices: [10]
Text: AAAAABAAAAA
Pattern: AAAA
Found at indices: [0, 1, 2, 6, 7]

6. KMPアルゴリズムの計算量解析

KMPアルゴリズムの全体の計算量は、piテーブル構築のステップと検索本体のステップを合計したものになります。

  • piテーブル構築: 前述の通り、これは O(m) の時間で完了します。
  • 検索本体: こちらも線形時間 O(n) で完了します。

したがって、KMPアルゴリズム全体の計算量は O(n + m) となります。これは、テキストとパターンの長さに比例する時間で検索が完了することを意味し、非常に効率的です。特に、ナイーブ法が最悪ケースで O(nm) かかるのと比較すると、KMPアルゴリズムの優位性は明らかです。

なぜ検索本体が O(n) なのか？

検索本体の while ループ (while i < n) を見てみましょう。
ループ内では、大きく分けて2つのケースがあります。

  1. 文字が一致する場合 (pattern[j] == text[i]): このとき、i と j は両方とも1つ増えます (i++, j++)。テキストポインタ i は必ず前進します。
  2. 文字が一致しない場合 (pattern[j] != text[i]):
    • j > 0 の場合 (j = pi[j-1])：パターンポインタ j は減少します。テキストポインタ i はそのままです。
    • j == 0 の場合 (i++)：テキストポインタ i が1つ増えます。パターンポインタ j は0のままです。

テキストポインタ i は、文字が一致するか、または j == 0 で不一致が発生した場合にのみ増加します。いずれの場合も、i は決して減少しません。i は最大で n 回（0からn-1まで）増加する可能性があります。

パターンポインタ j は、文字が一致した場合に増加するか、不一致かつ j > 0 の場合に piテーブルの値に基づいて減少します。
j の値は常に 0 から m の間にあります（パターン全体一致で j が m になった後、pi[m-1] に戻されるため）。
j が増加するのは、P[j] == T[i] の場合だけです。このとき i も増加します。i の最大増加量は n ですから、j の合計増加量も高々 O(n) + O(m)（初期値と一致時の増加）になります。
j が減少するのは、P[j] != T[i] かつ j > 0 の場合です。j の減少は、必ずそれ以前に j が増加した分を「巻き戻す」形で行われます。例えば、j が 5 から pi[4] に減少した場合、j はそれ以前に少なくとも 5 まで増加していたはずです。j の値は 0 より小さくなることはありません。したがって、j の合計減少量は、j の合計増加量を超えることはありません。

テキストポインタ i は最大 n 回進みます。パターンポインタ j は、合計で高々 O(n) 回増加し、その増加に対応して O(n) 回減少する可能性があります（より厳密には、j の合計増加量は O(n) であり、減少量は O(m) です。なぜなら、j が減少するときの新しい値 pi[j-1] は常に j-1 より小さいか等しいため、j が0になるまで減少する過程は O(j) ステップで、その合計は m を超えません。しかし、文字一致による j の増加は i の増加と連動しており、i が n 回しか増加しないため、j の合計増加量も O(n) に限られます。したがって、j の総移動量（増加と減少を合わせたステップ数）は O(n + m) となり、ループ全体は O(n+m) 回の比較と操作で完了します。ただし、i の増加は O(n) 回、j の変化は O(n+m) 回のステップに対応し、各ステップは定数時間なので、全体で O(n+m) となります。特に、テキストを読み進めるポインタ i が決して戻らないため、テキストの各文字は高々2回程度（P[j] == T[i] で一致、または P[0] != T[i] で不一致）しか参照されないことになります。

7. KMPアルゴリズムの応用

KMPアルゴリズムは単純な文字列検索だけでなく、いくつかの関連する問題にも応用できます。

  • 文字列の繰り返しパターンの検出: piテーブル自体は、パターン P の各接頭辞における繰り返し構造を捉えています。例えば、pi[m-1] の値 k は、パターン P が長さ m の文字列であり、その最初の k 文字が最後の k 文字と一致することを示します。もし m が m-k で割り切れるなら、パターン P は長さ m-k の部分文字列の繰り返しで構成されている可能性があります。
  • テキスト中の最長接頭辞かつ接尾辞の検出: KMPアルゴリズムの考え方は、テキスト中の特定の区間 T[0...i] について、その中で「接頭辞かつ接尾辞」であるような最長の部分文字列を見つける問題に応用できます。これは、文字列圧縮やバイオインフォマティクスなどの分野で利用されることがあります。
  • 複数のパターンの検索: Aho-Corasickアルゴリズムのような高度なマルチパターン検索アルゴリズムは、KMPの失敗関数の概念を拡張して構築されています。

8. 実装のヒントと注意点

KMPアルゴリズムを実際に実装する際のいくつかのヒントと注意点です。

  • 0-based vs 1-based インデックス: 本記事では0-basedインデックス（配列の最初の要素がインデックス0）を前提に説明しました。多くのプログラミング言語も0-basedですが、1-basedインデックスを使用する言語や環境で実装する場合は、インデックスのオフセットに注意が必要です。piテーブルのサイズやアクセス方法が変わってきます。
  • テーブルサイズの確保: パターン P の長さ m に合わせて、piテーブルは正確に m サイズの配列として確保する必要があります。
  • pi[0] の初期化: piテーブルの最初の要素 pi[0] は常に 0 で初期化される点に注意してください。アルゴリズムのループは通常インデックス 1 から開始します。
  • 不一致時の j の更新: 不一致時 (P[i] != P[j]) に j を pi[j-1] に更新する操作は、j > 0 の場合にのみ行います。j == 0 の場合は、パターン先頭との比較で不一致となったことを意味するため、パターンをずらすのではなく、テキストポインタ i を進めます。
  • パターン全体一致時の j の更新: パターン全体が見つかった場合 (j == m) も、次の検索を継続するために j を pi[m-1] に更新することを忘れないでください。これにより、重複する可能性のあるパターン出現箇所も正しく検出できます。

9. KMPと他の文字列検索アルゴリズムとの比較

文字列検索アルゴリズムはKMPだけではありません。代表的なものとして、以下のようなものがあります。

  • Boyer-Mooreアルゴリズム: こちらも広く使われている効率的なアルゴリズムです。Boyer-Mooreはパターンの末尾から比較を開始し、不一致が発生した場合に「悪い文字ルール (Bad Character Rule)」と「良い接尾辞ルール (Good Suffix Rule)」という2つのルールに基づいてパターンを大きくずらすことを試みます。多くの場合、KMPよりも高速に動作しますが、最悪計算量は O(nm) です（ただし、線形時間で動作する改良版もあります）。Boyer-Mooreは平均ケースでの性能に優れますが、KMPは最悪ケースでも O(n+m) の計算量が保証されるという点で優れています。
  • Rabin-Karpアルゴリズム: ハッシュ関数を利用して文字列の比較を高速化するアルゴリズムです。衝突（異なる文字列が同じハッシュ値を持つこと）の可能性があり、それを適切に処理する必要があります。平均計算量は O(n+m) ですが、最悪計算量は O(nm) になる可能性があります（ハッシュ関数の選択に依存）。実装は比較的シンプルですが、ハッシュ関数の設計が重要になります。

KMPアルゴリズムは、piテーブルという追加のメモリ（O(m)）を使用しますが、テキストの長さに線形な時間で検索が完了するという最悪計算量の保証がある点が強みです。特に、テキストやパターンに繰り返しが多い場合にその性能を発揮します。

10. まとめ：KMPマスターへの道

本記事では、KMPアルゴリズムの詳細を、ナイーブ法との比較から始まり、核心であるpiテーブルの定義と構築、そして検索アルゴリズム本体、計算量解析、応用、実装のヒントまで、網羅的に解説しました。

KMPアルゴリズムの美しさは、比較が失敗した際に、すでに分かっている情報（一致していた部分文字列の構造）を最大限に利用して、次に比較を開始すべきパターン中の位置を賢く決定する点にあります。この「賢いずらし」を可能にするのが、パターンの各接頭辞における「最も長い接頭辞かつ接尾辞の長さ」を記録したpiテーブルです。

piテーブルの構築アルゴリズムと、そのテーブルを利用した検索アルゴリズムは、最初は少し複雑に感じられるかもしれません。しかし、それぞれのステップで「なぜそのように動くのか」「何のためにその情報を計算しているのか」を、パターンやテキストの具体的な例を追って理解することで、その仕組みが見えてくるはずです。特に、不一致時にパターンポインタ j が pi[j-1] に戻る操作の意味するところを深く理解することが、KMPマスターへの鍵となります。

KMPアルゴリズムは、単なる特定の文字列検索アルゴリズムの一つというだけでなく、過去の情報に基づいて未来のステップを決定するという、より広範なアルゴリズム設計の思想を学ぶ上でも非常に良い例となります。動的計画法的な考え方や、ポインタの巧妙な操作によって線形時間を達成するメカニズムは、他の多くのアルゴリズムを理解する上での基盤となります。

さあ、あなたはこれでKMPアルゴリズムの理論的な基盤と実装方法を学びました。ぜひ、実際にコードを書いて動かしてみて、様々なテキストとパターンでその動作を確認してみてください。理解が深まるにつれて、この洗練されたアルゴリズムの真価を実感できるでしょう。KMPアルゴリズムを自信を持って使いこなし、文字列検索の世界での冒険を楽しんでください！

コメントする

メールアドレスが公開されることはありません。 ※ が付いている欄は必須項目です

上部へスクロール