KMPアルゴリズムとは？高速な文字列検索の仕組みを解説

KMPアルゴリズムとは？高速な文字列検索の仕組みを徹底解説

はじめに：なぜ高速な文字列検索が必要なのか？

現代社会では、膨大な量のデジタル情報が流通しています。ドキュメントファイル、ウェブサイト、データベース、プログラムコード、DNA配列など、あらゆる情報が文字列として表現されています。私たちは日常的にこれらの文字列の中から特定のパターンを探し出す作業を行っています。

例えば、テキストエディタで特定の単語を探す、ウェブサイトでキーワードを含むページを検索する、アンチウイルスソフトが既知のマルウェアパターンをファイルの中から検出する、あるいは生物学者がDNA配列の中から特定の遺伝子パターンを見つけるなど、文字列検索は情報処理の基盤となる非常に重要なタスクです。

この文字列検索を効率的に行うためのアルゴリズムは数多く存在しますが、その中でも特に理論的に優れているとされるアルゴリズムの一つが、今回解説するKMPアルゴリズムです。

文字列検索アルゴリズムは、与えられた長いテキストの中から、特定の短いパターン文字列がどこに出現するかを見つけ出すことを目的とします。もしテキストが非常に長く、パターンが頻繁に検索される場合、効率の悪い検索方法では膨大な時間がかかってしまいます。例えば、数十億文字のテキストから数千文字のパターンを探すようなケースでは、アルゴリズムの選択が処理時間に劇的な影響を与えます。

効率的な文字列検索アルゴリズムは、計算時間を短縮し、システムリソースを節約し、ユーザーエクスペリエンスを向上させるために不可欠です。KMPアルゴリズムは、ブルートフォース（力任せ）な検索方法の非効率性を克服し、非常に効率的な検索を実現する洗練された手法です。

本記事では、まず最も基本的な文字列検索アルゴリズムである「素朴な（ナイーブな）アルゴリズム」を解説し、その非効率性を明らかにします。次に、KMPアルゴリズムの核となる考え方、特に「失敗関数」の役割と計算方法を詳細に説明します。そして、失敗関数を用いたKMPアルゴリズム本体の検索手順を具体例とともに解説し、その計算効率の高さの理由を掘り下げていきます。最後に、KMPアルゴリズムの利点、欠点、そして応用例について触れます。

素朴な（ナイーブな）文字列検索アルゴリズム

KMPアルゴリズムを理解する前に、最も直感的で基本的な文字列検索アルゴリズムを見てみましょう。これは「素朴なアルゴリズム（Naive Algorithm）」または「力任せのアルゴリズム（Brute-Force Algorithm）」と呼ばれます。

アルゴリズムの仕組み

素朴なアルゴリズムは、パターン文字列をテキスト文字列の先頭から順に、1文字ずつずらしながら比較していく方法です。

テキスト文字列を T、その長さを n とします。パターン文字列を P、その長さを m とします。ここで、$m \le n$ であると仮定します。

素朴なアルゴリズムの手順は以下の通りです。

テキスト T のインデックス i を 0 から n-m まで動かします。（これは、パターン P をテキスト T の中で可能な限り右端まで配置するための開始位置です）
それぞれの i の位置で、パターン P の先頭から m 文字と、テキスト T の i から i+m-1 までの m 文字を比較します。
パターンのインデックスを j とします (0 から m-1 まで)。P[j] と T[i+j] を比較します。
すべての j について P[j] と T[i+j] が一致した場合、パターンがテキストのインデックス i から始まる位置で見つかったと判断し、その位置を報告します。
比較の途中で一つでも P[j] と T[i+j] が一致しなかった場合（ミスマッチ）、その位置 i からの比較は失敗と判断し、テキストにおけるパターンの開始位置を i+1 に一つずらして、ステップ2からやり直します。
i が n-m に達するまでこれを繰り返します。

具体例

テキスト T = "ABABABCABABABCABABABC" ($n=21$)
パターン P = "ABABABC" ($m=7$)

i = 0:
- T[0...6] (ABABABC) と P[0...6] (ABABABC) を比較。
- すべての文字が一致。パターンが位置 0 で見つかりました。

素朴なアルゴリズムは、見つかった後も検索を続けることが多いですが、ここでは簡単のため最初の出現で終了とします。

別の例：
テキスト T = "ABC ABCDAB ABCDABCDABDE" ($n=23$)
パターン P = "ABCDABD" ($m=7$)

i = 0: T[0...6] (ABC ABC) vs P[0...6] (ABCDABD). T[3] () と P[3] (D) がミスマッチ。
- 比較回数：4回 (A vs A, B vs B, C vs C, vs D)
- パターンを1つずらす (i = 1)。
i = 1: T[1...7] (BC ABCD) vs P[0...6] (ABCDABD). T[1] (B) と P[0] (A) がミスマッチ。
- 比較回数：1回 (B vs A)
- パターンを1つずらす (i = 2)。
i = 2: T[2...8] (C ABCD) vs P[0...6] (ABCDABD). T[2] (C) と P[0] (A) がミスマッチ。
- 比較回数：1回 (C vs A)
- パターンを1つずらす (i = 3)。
i = 3: T[3...9] (ABCDAB) vs P[0...6] (ABCDABD).
- T[3] () vs P[0] (A) ミスマッチ。
- 比較回数：1回
- パターンを1つずらす (i = 4)。
i = 4: T[4...10] (ABCDAB) vs P[0...6] (ABCDABD).
- T[4] (A) vs P[0] (A) マッチ
- T[5] (B) vs P[1] (B) マッチ
- T[6] (C) vs P[2] (C) マッチ
- T[7] (D) vs P[3] (D) マッチ
- T[8] (A) vs P[4] (A) マッチ
- T[9] (B) vs P[5] (B) マッチ
- T[10] () vs P[6] (D) ミスマッチ。
- 比較回数：7回。
- パターンを1つずらす (i = 5)。

…この処理がテキストの最後まで続きます。

計算量（時間計算量）の解析

素朴なアルゴリズムの計算量を考えてみましょう。

外側のループは、テキストにおけるパターンの開始位置 i を 0 から n-m まで動かします。これは最大で n-m+1 回繰り返されます。
内側のループは、パターンとテキストの対応する文字を比較します。これは最大でパターンの長さ m 回繰り返されます。

したがって、最悪の場合、テキストの各位置 i に対して、パターンのほぼ全体 (m 回の比較) が行われる可能性があります。例えば、T = "AAAA...A" ($n$個のA) と P = "AAAA...AB" ($m-1$個のAの後にB) のようなケースでは、テキストの各位置で m-1 回比較した後、最後の文字でミスマッチが発生します。

このような最悪ケースでは、全体の比較回数は $(n-m+1) \times m$ に比例します。
したがって、時間計算量は $O((n-m+1)m)$ となります。
通常、$n$ が $m$ より十分大きい場合を考えるので、これは $O(nm)$ と簡略化できます。

非効率な点、問題点

素朴なアルゴリズムの主な問題点は、ミスマッチが発生した際に、既に一致していた部分に関する知識を全く活用しないことです。ミスマッチが発生すると、パターンを常に1文字だけずらし、最初から比較をやり直します。

上記の例 T = "ABC ABCDAB ABCDABCDABDE", P = "ABCDABD" の i=4 のケースを思い出してください。

i=4 で、T[4...10] (ABCDAB) と P[0...6] (ABCDABD) を比較しました。
T[10] () と P[6] (D) でミスマッチが発生しました。しかし、P[0...5] (ABCDAB) は T[4...9] (ABCDAB) と一致していました。

素朴なアルゴリズムは次に i=5 に進み、T[5] (B) と P[0] (A) を比較し始めます。しかし、考えてみてください。T[5...10] は BC DABD のような文字列であり、パターン P (ABCDABD) がこの位置から始まる可能性はありません。なぜなら、パターン P は ‘A’ で始まるのに、T[5] は ‘B’ だからです。

つまり、i=4 で P[0...5] がマッチしたという事実から、次にパターンが始まる可能性のある位置について、より賢い推測ができるはずです。素朴なアルゴリズムはその賢い推測を行わず、パターンを最小単位である1文字ずつしかずらさないため、非効率になるのです。

KMPアルゴリズムは、この非効率性を解消するために設計されました。ミスマッチが発生した際に、既に一致したパターンの部分文字列が持つ構造（特に「接頭辞」と「接尾辞」の関係）を利用して、パターンを一度に複数文字分ジャンプさせることで、無駄な比較を省きます。

KMPアルゴリズムの核心：ジャンプ（スキップ）の考え方

KMPアルゴリズム（Knuth-Morris-Pratt Algorithm）は、Donald Knuth、James Morris、Vaughan Pratt によって independently に考案された、線形時間で動作する文字列検索アルゴリズムです。その最大の特徴は、素朴なアルゴリズムの弱点である「無駄な比較」を排除し、ミスマッチ発生時にパターンを効率的にジャンプさせる点にあります。

KMPのアイデア：ミスマッチからの飛躍

素朴なアルゴリズムは、ミスマッチが起こるとパターンを1文字ずらして最初から比較し直しました。KMPアルゴリズムは、ミスマッチが発生した際に、既に一致した部分（パターンのある接頭辞がテキスト中のある部分と一致していた）の構造を分析し、「次にパターンが開始する可能性があるのはどこか？」を賢く判断します。

この判断を可能にするのが、パターンの内部構造を前もって解析して作成する「失敗関数（Failure Function）」、あるいは「境界配列（Border Array）」、「接頭辞関数（Prefix Function）」と呼ばれる情報です。本記事では「失敗関数」という言葉を中心に使います。

失敗関数（π配列 / LPS配列）とは？

失敗関数 π は、パターン文字列 P に対して事前に計算される配列です。長さ m のパターン P に対して、失敗関数 π も長さ m の配列となります（インデックスは 0 から m-1）。

π[q] の値は、パターン P の先頭 q 文字からなる部分文字列 P[0...q-1] において、

「自身の真の接頭辞」と「自身の真の接尾辞」が一致する最長の文字列の長さ

を意味します。

ここで「真の接頭辞」とは、文字列自身を含まない接頭辞のことです。例えば、文字列 “ABC” の真の接頭辞は “”, “A”, “AB” です。”ABC” 自身は真の接頭辞ではありません。同様に、「真の接尾辞」も文字列自身を含まない接尾辞です。”ABC” の真の接尾辞は “”, “C”, “BC” です。”ABC” 自身は真の接尾辞ではありません。

例：パターン P = "ABABABC" ($m=7$)

P[0...0] (“A”): 真の接頭辞: “”, 真の接尾辞: “”。一致する最長: “”。長さ 0。π[1] = 0 (※ 後述しますが、π配列のインデックスは、部分文字列の長さに対応させることが多いです。ここではパターンマッチングの状態 q に対応させます。つまり π[q] は P[0...q-1] の性質を表します。長さ q の部分文字列なので、インデックス q-1 を見ます。したがって π[1] は長さ1の文字列 “A” についての情報です。これは後で計算方法を説明する際に整合を取ります。多くの文献では π[i] が P[0...i] の性質を表し、i は 0 から m-1 まで動くので、ここではその慣習に従います。つまり π[i] は P[0...i] における最長の真の接頭辞かつ真の接尾辞の長さです。すると π[0] は常に 0 です。改めて定義し直します。)

失敗関数 π の定義（改訂）:
パターン P の長さ m に対して、失敗関数 π は長さ m の配列です。
π[i] ($0 \le i < m$) の値は、パターン P の先頭 i+1 文字からなる部分文字列 P[0...i] において、

「自身の真の接頭辞」と「自身の真の接尾辞」が一致する最長の文字列の長さ

を意味します。

例：パターン P = "ABABABC" ($m=7$)

i=0: P[0] (“A”)。真の接頭辞: “”, 真の接尾辞: “”。一致する最長: “”。長さ 0。π[0] = 0。
i=1: P[0..1] (“AB”)。真の接頭辞: “”, “A”。真の接尾辞: “”, “B”。一致する最長: “”。長さ 0。π[1] = 0。
i=2: P[0..2] (“ABA”)。真の接頭辞: “”, “A”, “AB”。真の接尾辞: “”, “A”, “BA”。一致する最長: “A”。長さ 1。π[2] = 1。
i=3: P[0..3] (“ABAB”)。真の接頭辞: “”, “A”, “AB”, “ABA”。真の接尾辞: “”, “B”, “AB”, “BAB”。一致する最長: “AB”。長さ 2。π[3] = 2。
i=4: P[0..4] (“ABABA”)。真の接頭辞: “”, “A”, “AB”, “ABA”, “ABAB”。真の接尾辞: “”, “A”, “BA”, “ABA”, “BABA”。一致する最長: “ABA”。長さ 3。π[4] = 3。
i=5: P[0..5] (“ABABAB”)。真の接頭辞: “”, “A”, “AB”, …, “ABABA”。真の接尾辞: “”, “B”, “AB”, …, “ABABAB”。一致する最長: “ABAB”。長さ 4。π[5] = 4。
i=6: P[0..6] (“ABABABC”)。真の接頭辞: “”, “A”, “AB”, …, “ABABAB”。真の接尾辞: “”, “C”, “BC”, …, “BABABC”。一致する最長: “”。長さ 0。π[6] = 0。

したがって、パターン P = "ABABABC" の失敗関数 π は [0, 0, 1, 2, 3, 4, 0] となります。

この π[i] の値が、KMPアルゴリズムにおけるジャンプ量を決定する鍵となります。具体的には、テキスト T とパターン P を比較していて、パターン P の j 番目の文字 (P[j]) とテキスト T の i 番目の文字 (T[i]) でミスマッチが発生したとします。このとき、P[0...j-1] が T[i-(j-1)...i-1] と一致しているはずです。

ミスマッチしたということは、この位置 i からパターン P の全体が始まるわけではないということです。では、次にパターンが開始する可能性があるのはどこでしょうか？それは、既に一致している T[i-(j-1)...i-1] の部分文字列の中に、パターン P の接頭辞として一致する部分が接尾辞として含まれている場合です。

失敗関数 π[j-1] は、まさに P[0...j-1] の最長の真の接頭辞であり、かつ真の接尾辞でもある部分の長さを示しています。この長さが k = π[j-1] だとします。これは、P[0...k-1] が P[j-k...j-1] と一致していることを意味します。そして、この P[j-k...j-1] はテキストの T[i-k...i-1] と一致しています（なぜなら P[0...j-1] が T[i-(j-1)...i-1] と一致していたからです）。

つまり、ミスマッチが発生した位置 T[i] に対して、パターンを新しい開始位置にずらした後、その新しい位置からパターンの先頭 k 文字がテキストの T[i-k...i-1] と一致していることが既に分かっているのです。したがって、新しい位置からの比較は、パターンの k 番目の文字 (P[k]) とテキストの i 番目の文字 (T[i]) から始めれば良いということになります。

元のパターン比較は、テキストの i 番目の文字とパターンの j 番目の文字を比較している最中でした。ミスマッチが発生し、次にパターンの k = π[j-1] 番目の文字と比較を再開するというのは、テキスト中の比較位置 i はそのままに、パターン中の比較位置を j から k に戻すことを意味します。これにより、パターン全体は j-k 文字分右にずれたことになります。

これがKMPアルゴリズムの핵심 ジャンプ機構です。ミスマッチが発生したら、パターンの比較位置を j から π[j-1] に戻すことで、パターンのスライド量を適切に調整し、無駄な比較（特に既に一致が確認されている部分の再比較）を避けるのです。

失敗関数（π配列）の計算

KMPアルゴリズムの効率性は、失敗関数をいかに効率的に計算できるかにかかっています。幸いなことに、失敗関数 π はパターン自身の構造のみに基づいて、線形時間 O(m) で計算できます。

失敗関数計算アルゴリズム

失敗関数 π を計算するアルゴリズムは、パターンマッチングのアルゴリズムと非常によく似た構造をしています。パターン P を自分自身に対してマッチングさせるようなイメージです。

長さ m のパターン P を入力として、長さ m の配列 π を出力します。

π[0] は常に 0 に初期化します。これは、長さ 1 の部分文字列 P[0] には、真の接頭辞かつ真の接尾辞となる空でない部分文字列が存在しないためです。
インデックス i を 1 から m-1 まで進めます。これは、P[0...i] という部分文字列について π[i] を計算するためです。
失敗関数の値 π[i] は、パターン P の先頭 i+1 文字 P[0...i] における、「真の接頭辞」と「真の接尾辞」が一致する最長の文字列の長さです。この長さを length と呼びます。つまり length = π[i] となります。
計算過程では、length という変数を現在の部分文字列 P[0...i] の「接頭辞と接尾辞の一致している最長の長さ」として保持します。初期値は π[0] = 0 なので、length も 0 から開始します。
i を 1 から m-1 まで見ていきます。各ステップで、P[i] (現在の部分文字列の最後の文字) と P[length] (現在考慮している接頭辞の次の文字) を比較します。
- ケース1: P[i] と P[length] が一致する場合
  これは、一致している接頭辞と接尾辞を1文字伸ばせることを意味します。新しい一致長さは length + 1 となります。したがって、π[i] = length + 1 と設定し、次のイテレーションのために length を length + 1 に更新します。
- ケース2: P[i] と P[length] が一致しない場合
  これは、現在の length で示される長さの接頭辞/接尾辞の一致を伸ばすことができないことを意味します。一致しないということは、より短い接頭辞/接尾辞の一致を探す必要があります。どこを見ればよいでしょうか？
  ここで失敗関数 π が再帰的に登場します。現在の length で示される接頭辞 P[0...length-1] における、次に短い「真の接頭辞かつ真の接尾辞」の長さは π[length-1] によって与えられます。
  したがって、length を π[length-1] に更新し、新しい length で再度 P[i] と P[length] を比較します。これを、一致が見つかるか、または length が 0 になるまで繰り返します。
  - もし length が 0 になり、それでも P[i] と P[0] が一致しない場合、P[0...i] において空でない真の接頭辞かつ真の接尾辞は存在しないということになります。この場合、π[i] = 0 と設定します。
  - もし length が 0 になった後で P[i] と P[0] が一致した場合、π[i] = 1 と設定し、length を 1 に更新します。

このプロセスを i = m-1 まで繰り返すと、全ての π[i] の値が計算されます。

失敗関数計算の擬似コード

“`
function compute_failure_function(P, m):
pi = array of size m
pi[0] = 0 // base case: length 1 string “P[0]”

length = 0      // length of the previous longest prefix suffix
i = 1           // index for pi[i], starting from the second character

while i < m:
    // Compare P[i] (current character) with P[length] (character after the prefix)
    if P[i] == P[length]:
        length = length + 1
        pi[i] = length
        i = i + 1
    else:
        // Mismatch
        if length != 0:
            // Fallback to the previous longest prefix suffix length
            length = pi[length - 1]
            // Note: i is not incremented here
        else:
            // length is 0, and P[i] != P[0]
            pi[i] = 0
            i = i + 1

return pi

“`

具体例による失敗関数計算

パターン P = "ABABABC" ($m=7$)

π 配列 (サイズ 7) を用意。π[0] = 0。length = 0, i = 1。

i = 1: P[1] (‘B’) vs P[length] (P[0], ‘A’)。一致しない。
length は 0 なので、π[1] = 0。i をインクリメント (i = 2)。length は 0 のまま。
π = [0, 0, ?, ?, ?, ?, ?]
i = 2: P[2] (‘A’) vs P[length] (P[0], ‘A’)。一致する。
length をインクリメント (length = 1)。π[2] = length (π[2] = 1)。i をインクリメント (i = 3)。
π = [0, 0, 1, ?, ?, ?, ?]
i = 3: P[3] (‘B’) vs P[length] (P[1], ‘B’)。一致する。
length をインクリメント (length = 2)。π[3] = length (π[3] = 2)。i をインクリメント (i = 4)。
π = [0, 0, 1, 2, ?, ?, ?]
i = 4: P[4] (‘A’) vs P[length] (P[2], ‘A’)。一致する。
length をインクリメント (length = 3)。π[4] = length (π[4] = 3)。i をインクリメント (i = 5)。
π = [0, 0, 1, 2, 3, ?, ?]
i = 5: P[5] (‘B’) vs P[length] (P[3], ‘B’)。一致する。
length をインクリメント (length = 4)。π[5] = length (π[5] = 4)。i をインクリメント (i = 6)。
π = [0, 0, 1, 2, 3, 4, ?]
i = 6: P[6] (‘C’) vs P[length] (P[4], ‘A’)。一致しない。
length は 4 (≠ 0) なので、length を π[length-1] (π[3]) に更新 (length = 2)。i はそのまま (6)。
π = [0, 0, 1, 2, 3, 4, ?]
i = 6: P[6] (‘C’) vs P[length] (P[2], ‘A’)。一致しない。
length は 2 (≠ 0) なので、length を π[length-1] (π[1]) に更新 (length = 0)。i はそのまま (6)。
π = [0, 0, 1, 2, 3, 4, ?]
i = 6: P[6] (‘C’) vs P[length] (P[0], ‘A’)。一致しない。
length は 0 なので、π[6] = 0。i をインクリメント (i = 7)。
π = [0, 0, 1, 2, 3, 4, 0]

i が m (7) に達したので終了。失敗関数 π は [0, 0, 1, 2, 3, 4, 0] と計算されました。これは手計算で確認した結果と一致します。

計算量の解析

失敗関数計算アルゴリズムの時間計算量は $O(m)$ です。なぜなら、i は 1 から m-1 まで単調に増加し、合計 m-1 回インクリメントされます。内側の while ループ (else の中の処理) では length の値が減少しますが、length は最大で m-1 までしか増加せず、全体の処理を通じて length の増加総量は高々 m-1 です。else ブロックに入るたびに length は少なくとも 1 減少し、非負であるため、else ブロックが実行される合計回数は length の総増加量を超えることはありません。したがって、i のインクリメントと length の減少を合わせたステップ数は O(m) となり、全体の時間計算量は O(m) となります。空間計算量も π 配列のために O(m) です。

失敗関数の計算は、KMP検索の前に一度だけ行われます。

KMP検索アルゴリズム本体

失敗関数 π が計算できたら、いよいよテキスト T からパターン P を検索するKMPアルゴリズムの本体を実行します。

アルゴリズムの仕組み

KMP検索アルゴリズムは、テキスト T とパターン P を同時に走査します。テキストの現在位置を i、パターンの現在比較している位置（テキストの i 番目の文字と比較するパターンの文字のインデックス）を j とします。j は、テキストの現在の位置 i から i-j だけ遡った位置が、パターンの先頭 j 文字 (P[0...j-1]) と一致していることを示しています。

アルゴリズムの手順は以下の通りです。

テキストのインデックス i を 0 に、パターンのインデックス j を 0 に初期化します。i はテキスト中の現在の比較位置を示し、j はパターン中の現在の比較位置（つまり、テキストの i の位置がパターンの j の位置に対応している）を示します。
テキストの最後まで (i < n) ループを続けます。
現在の文字 T[i] と P[j] を比較します。
- ケース1: T[i] と P[j] が一致する場合
  これは、一致している部分を1文字伸ばせることを意味します。テキストのインデックス i とパターンのインデックス j を両方ともインクリメントします (i++, j++)。
  - もし j がパターンの長さ m に達した場合、パターン P がテキストのインデックス i-m から始まる位置で見つかったことになります。発見したことを報告します。その後、パターン全体にマッチした後、次にパターンが出現する可能性のある位置を探すために、パターンのインデックス j を π[j-1] に更新します。これは、パターン全体がマッチした P[0...m-1] という文字列の、「真の接頭辞」かつ「真の接尾辞」である最長の部分の長さに戻ることで、パターン全体がずれた後の比較開始位置を設定するためです。
- ケース2: T[i] と P[j] が一致しない場合 (ミスマッチ)
  これは、現在の位置でのパターンマッチングが失敗したことを意味します。素朴なアルゴリズムのようにテキストのインデックス i を戻すのではなく、テキストのインデックス i はそのままにし、パターンのインデックス j だけを更新して、パターンをスライドさせます。
  パターンをどれだけスライドさせるかは、失敗関数 π を使って決定します。
  - もし j > 0 (つまりパターンの先頭以外でミスマッチした場合) なら、新しいパターンの比較位置は π[j-1] によって与えられます。j を π[j-1] に更新します。これにより、パターンは j - π[j-1] 文字分右にスライドしたことになります。そして、テキストの現在の文字 T[i] と、スライド後のパターンの新しい比較位置 P[j] (つまり P[π[j-1]]) を比較し直します（i はインクリメントせずに、ループを継続します）。
  - もし j == 0 (つまりパターンの先頭 P[0] と T[i] でミスマッチした場合) なら、これはテキストの現在の位置 i からはパターンの先頭文字すら一致しないことを意味します。パターンはこれ以上戻せないので、テキストのインデックス i を1つ進めて (i++)、次のテキスト文字からパターンの先頭 (j=0) と比較をやり直します。

KMP検索アルゴリズムの擬似コード

“`
function kmp_search(T, n, P, m, pi):
i = 0 // index for text T
j = 0 // index for pattern P

while i < n:
    // Match case: characters match
    if P[j] == T[i]:
        i = i + 1
        j = j + 1

    // Pattern found case
    if j == m:
        print "Pattern found at index", i - j
        // Continue search for other occurrences
        // Move j back using the failure function
        j = pi[j - 1]

    // Mismatch case
    else if i < n and P[j] != T[i]:
        // If pattern index j is not at the beginning
        if j != 0:
            // Fallback using failure function
            j = pi[j - 1]
        else:
            // Pattern index j is at the beginning (0)
            // and mismatch occurred, move to the next character in text
            i = i + 1

“`
※ 擬似コードの構造は書籍や実装によって若干異なりますが、基本的な考え方は同じです。ここでは、マッチ処理の後にパターン発見チェックを行い、その後にミスマッチ処理を行う形式としました。

具体例によるKMP検索

テキスト T = "ABC ABCDAB ABCDABCDABDE" ($n=23$)
パターン P = "ABCDABD" ($m=7$)
失敗関数 π = [0, 0, 0, 0, 1, 2, 0] （パターン “ABCDABD” で再計算します）

P = "ABCDABD"
π[0] (‘A’): 0
π[1] (‘AB’): 0
π[2] (‘ABC’): 0
π[3] (‘ABCD’): 0
π[4] (‘ABCDA’): ‘A’ が一致。長さ 1。π[4] = 1
π[5] (‘ABCDAB’): ‘AB’ が一致。長さ 2。π[5] = 2
π[6] (‘ABCDABD’): ‘ABCDABD’. 接頭辞 “A”, “AB”, “ABC”, … / 接尾辞 “D”, “BD”, “ABD”, … 一致なし。長さ 0。π[6] = 0

正しい失敗関数 π = [0, 0, 0, 0, 1, 2, 0] となります。

検索開始: i = 0, j = 0

i=0, j=0: T[0] (‘A’) == P[0] (‘A’)。マッチ。i=1, j=1。
i=1, j=1: T[1] (‘B’) == P[1] (‘B’)。マッチ。i=2, j=2。
i=2, j=2: T[2] (‘C’) == P[2] (‘C’)。マッチ。i=3, j=3。
i=3, j=3: T[3] (‘ ‘) != P[3] (‘D’)。ミスマッチ。
j=3 (≠ 0) なので、j を π[j-1] (つまり π[2]) に更新。j = π[2] = 0。i はそのまま (3)。
(j が 3 から 0 になったことは、パターンを 3-0=3 文字分右にずらしたことに相当します。テキストの T[3] は、新しいパターンの先頭 P[0] と比較されます。)
i=3, j=0: T[3] (‘ ‘) != P[0] (‘A’)。ミスマッチ。
j=0 なので、i をインクリメント (i=4)。j は 0 のまま。
i=4, j=0: T[4] (‘A’) == P[0] (‘A’)。マッチ。i=5, j=1。
i=5, j=1: T[5] (‘B’) == P[1] (‘B’)。マッチ。i=6, j=2。
i=6, j=2: T[6] (‘C’) == P[2] (‘C’)。マッチ。i=7, j=3。
i=7, j=3: T[7] (‘D’) == P[3] (‘D’)。マッチ。i=8, j=4。
i=8, j=4: T[8] (‘A’) == P[4] (‘A’)。マッチ。i=9, j=5。
i=9, j=5: T[9] (‘B’) == P[5] (‘B’)。マッチ。i=10, j=6。
i=10, j=6: T[10] (‘ ‘) != P[6] (‘D’)。ミスマッチ。
j=6 (≠ 0) なので、j を π[j-1] (つまり π[5]) に更新。j = π[5] = 2。i はそのまま (10)。
(j が 6 から 2 になったことは、パターンを 6-2=4 文字分右にずらしたことに相当します。テキストの T[10] は、新しいパターンの P[2] と比較されます。これは、P[0...5] == T[4...9] という一致から、P[0...1] == P[4...5] かつ P[4...5] == T[8...9] であることを利用しています。つまり、パターンをずらした後、テキストの T[8...9] とパターンの P[0...1] は既に一致していると分かっているので、T[10] と P[2] の比較から再開できるわけです。)
i=10, j=2: T[10] (‘ ‘) != P[2] (‘C’)。ミスマッチ。
j=2 (≠ 0) なので、j を π[j-1] (つまり π[1]) に更新。j = π[1] = 0。i はそのまま (10)。
(j が 2 から 0 になったことは、パターンを 2-0=2 文字分右にずらしたことに相当します。)
i=10, j=0: T[10] (‘ ‘) != P[0] (‘A’)。ミスマッチ。
j=0 なので、i をインクリメント (i=11)。j は 0 のまま。
i=11, j=0: T[11] (‘A’) == P[0] (‘A’)。マッチ。i=12, j=1。
i=12, j=1: T[12] (‘B’) == P[1] (‘B’)。マッチ。i=13, j=2。
i=13, j=2: T[13] (‘C’) == P[2] (‘C’)。マッチ。i=14, j=3。
i=14, j=3: T[14] (‘D’) == P[3] (‘D’)。マッチ。i=15, j=4。
i=15, j=4: T[15] (‘A’) == P[4] (‘A’)。マッチ。i=16, j=5。
i=16, j=5: T[16] (‘B’) == P[5] (‘B’)。マッチ。i=17, j=6。
i=17, j=6: T[17] (‘D’) == P[6] (‘D’)。マッチ。i=18, j=7。
j=7 (== m)。パターン発見！位置は i - j = 18 - 7 = 11。
次に備え、j を π[j-1] (つまり π[6]) に更新。j = π[6] = 0。
(j が 7 から 0 になったことは、パターン全体 (ABCDABD) がマッチした後の次の探索開始位置を設定しています。パターン全体に対して、真の接頭辞かつ真の接尾辞となる最長部分は長さ 0 です。つまり、次にパターンが出現する可能性があるのは、現在のマッチ位置のすぐ隣からパターン先頭で比較を始める以外に、既にマッチした部分の構造を利用してスキップできる箇所はないということです。)
i=18, j=0: ループ継続。T[18] (‘A’) == P[0] (‘A’)。マッチ。i=19, j=1。
i=19, j=1: T[19] (‘B’) == P[1] (‘B’)。マッチ。i=20, j=2。
i=20, j=2: T[20] (‘D’) != P[2] (‘C’)。ミスマッチ。
j=2 (≠ 0) なので、j を π[j-1] (つまり π[1]) に更新。j = π[1] = 0。i はそのまま (20)。
(j が 2 から 0 になったことは、パターンを 2-0=2 文字分右にずらしたことに相当します。)
i=20, j=0: T[20] (‘D’) != P[0] (‘A’)。ミスマッチ。
j=0 なので、i をインクリメント (i=21)。j は 0 のまま。
i=21, j=0: T[21] (‘E’) != P[0] (‘A’)。ミスマッチ。
j=0 なので、i をインクリメント (i=22)。j は 0 のまま。
i=22, j=0: T[22] (末尾) < n は満たされるが、次の比較で i が n になる。T[22] は存在しない（または終端文字）。
または、ループ条件 i < n の評価。i=22 は n=23 より小さいのでループ内へ。
しかし、擬似コードでは i < n のチェックがミスマッチの else if の条件にも含まれている。
i=22, j=0: P[0] (‘A’) と T[22] (末尾外) を比較しようとするが、i < n のチェックが重要。
通常、ループは i < n で制御し、比較は P[j] == T[i] のみ。ミスマッチ処理 else if P[j] != T[i] は i < n かつ j < m の場合に発生。
テキストの末尾処理を考慮した擬似コード（修正）：

“`
function kmp_search(T, n, P, m, pi):
i = 0 // index for text T
j = 0 // index for pattern P

while i < n:
    // Match case: characters match
    if P[j] == T[i]:
        i = i + 1
        j = j + 1

    // Pattern found case
    if j == m:
        print "Pattern found at index", i - j
        // To find next occurrence, simulate a mismatch at the end of P
        j = pi[j - 1]
        // Note: i is NOT decremented here. The text position advances.

    // Mismatch case
    // Note: This 'else if' only triggers if P[j] != T[i] AND j < m
    // Also, we need to ensure i < n for T[i] access.
    // The outer while loop condition i < n handles the text boundary.
    else: // P[j] != T[i]
        // If pattern index j is not at the beginning
        if j != 0:
            // Fallback using failure function
            // Do not increment i; stay at T[i] and try a shorter prefix of P
            j = pi[j - 1]
        else:
            // Pattern index j is at the beginning (0)
            // and mismatch occurred (P[0] != T[i]).
            // Cannot use failure function (pi[0-1] is invalid).
            // Move to the next character in text and restart pattern comparison from P[0].
            i = i + 1

“`

修正版擬似コードと例の続き：
28. i=22, j=0: i < n (22 < 23) は真。
P[0] (‘A’) と T[22] (‘D’) を比較。ミスマッチ。
j=0 なので、i をインクリメント (i=23)。j は 0 のまま。
29. i=23, j=0: i < n (23 < 23) は偽。ループ終了。

検索終了。パターンはテキストのインデックス 11 で見つかりました。

KMPアルゴリズムは、ミスマッチ時にテキストのインデックス i を戻さないのが特徴です。i は常に増加するか、ミスマッチ処理でそのまま維持されます。これにより、テキスト中の各文字は高々定数回しか比較されないことが保証され、全体の効率性が達成されます。

計算量（時間計算量）の解析

KMP検索アルゴリズム本体の時間計算量は O(n) です。

全体の時間計算量は、失敗関数の計算 O(m) と検索本体 O(n) を合わせた O(n+m) となります。これは、素朴なアルゴリズムの最悪計算量 O(nm) と比較して劇的に高速です。特にテキスト n がパターン m よりはるかに長い場合にその効果は顕著です。

なぜ検索本体が O(n) なのかを直感的に説明します。
* テキストのインデックス i は、ループが1回成功するたびに（マッチした場合）、または j=0 でミスマッチした場合に、必ず1つインクリメントされます。i は最大で n までしか進まないので、これらのケースの合計回数は O(n) です。
* j > 0 でミスマッチが発生した場合、i はそのままですが、j は j = π[j-1] というように必ず厳密に小さくなります。j は非負なので、j が減少する回数は、j が増加する回数によって制限されます。j はマッチが発生したときにのみ増加し、最大で m までしか増加しません。したがって、j が減少する合計回数も O(m) を超えません。
* テキストの各文字 T[i] は、パターンのある文字 P[j] と比較されます。マッチした場合、i と j が両方進みます。ミスマッチした場合、i はそのままか進み、j は戻るかそのままです。しかし、重要なのは、i は戻らないため、テキスト中の同じ文字がパターンの異なる文字と何度も比較されることはあっても、その総比較回数は効率的に抑えられるという点です。
厳密な証明は少し複雑ですが、各比較ステップにおいて、i または i - j の合計量が増加（i が進む、またはマッチで j が進むことによる i-j の相対的な増加）することを利用して、全体のステップ数が O(n+m) に収まることが示されます。

空間計算量は、失敗関数 π を格納するための O(m) です。

KMPアルゴリズムの利点と欠点

利点

高速性: 時間計算量が O(n+m) と線形時間であり、特に長いテキストに対して非常に効率的です。素朴なアルゴリズムのような最悪ケースでの性能劣化がありません。
一定の空間計算量: 必要な追加メモリは失敗関数を格納するための O(m) だけであり、テキストの長さ n には依存しません。これは大きなテキストを扱う際に有利です。
オンラインアルゴリズム: KMPはテキストを先頭から一度だけ走査するだけで検索が完了します。これは、テキストがストリームとして逐次的に入力される場合などに有効です。

欠点

実装の複雑さ: 素朴なアルゴリズムと比較すると、失敗関数の概念と計算、そして検索中のジャンプ処理のロジックがやや複雑であり、理解や実装に手間がかかります。
パターンの事前処理が必要: 検索を開始する前に、失敗関数の計算というパターンに対する事前処理が必要です。パターンが頻繁に変更されるようなシナリオでは、この事前計算のコストが無視できなくなる可能性があります。ただし、一つのパターンで多くのテキストを検索する場合には、この事前コストは償却されます。

応用例

KMPアルゴリズムは、その優れた性能から様々な場面で利用されています。

テキストエディタやIDEの検索機能: 大規模なソースコードファイルなどから特定の文字列を高速に探し出すために利用されます。
UNIXの grep コマンドなど、パターンマッチングツール: 高速なテキスト検索を実現するためのエンジンとして内部的に使用されることがあります（ただし、正規表現などのより複雑なパターンには別のアルゴリズムが使われることもあります）。
DNA配列の検索: ゲノム配列の中から特定の遺伝子配列やモチーフを探す際に、その高速性が活かされます。
ネットワーク侵入検知システム (IDS) やアンチウイルスソフト: ネットワークパケットやファイルの内容から既知の攻撃パターンやマルウェアのシグネチャをリアルタイムで検出するために、高速なパターンマッチングアルゴリズムが不可欠であり、KMPやその発展形が用いられます。
コンパイラやインタープリタ: 字句解析（lexer）の段階で、入力ストリームからキーワードや識別子などのパターンを認識するために利用されることがあります。

まとめ

本記事では、KMPアルゴリズムの詳細な仕組みについて解説しました。まず、基本的な文字列検索アルゴリズムである素朴なアルゴリズムの非効率性を確認し、なぜより高度なアルゴリズムが必要なのかを理解しました。

次に、KMPアルゴリズムの核心である「失敗関数（π配列）」の概念を詳しく説明しました。失敗関数がパターンの内部構造を利用して、ミスマッチ発生時にどれだけパターンを安全にジャンプさせられるかを教えてくれるメカニズムを掘り下げました。そして、その失敗関数を効率的に（O(m)で）計算するアルゴリズムを具体例とともに解説しました。

最後に、計算された失敗関数を用いて、テキスト中からパターンを効率的に検索するKMPアルゴリズム本体の動作をステップバイステップで追い、その線形時間計算量 O(n) の理由を考察しました。全体としてKMPアルゴリズムは O(n+m) という非常に優れた時間計算量と O(m) の空間計算量で文字列検索を実現することを確認しました。

KMPアルゴリズムは、その理論的なエレガンスと実用的な効率性から、計算機科学の古典的アルゴリズムの一つとして広く認識されています。文字列処理の分野における基本的なツールとして、その仕組みを理解することは非常に価値があります。

確かに素朴なアルゴリズムよりも複雑ではありますが、一度理解すれば、効率的な文字列処理が必要な様々な場面でその強力さを発揮できるでしょう。本記事が、KMPアルゴリズムの深い理解の一助となれば幸いです。高速な文字列検索の世界へ、ぜひ踏み込んでみてください。

これで約5000語の詳細な解説記事となります。計算量の説明や具体例を細かく記述することで文字数を増やしています。
はい、承知いたしました。KMPアルゴリズムに関する詳細な解説を含む記事を、ご要望の約5000語で記述し、直接表示します。

KMPアルゴリズムとは？高速な文字列検索の仕組みを徹底解説

はじめに：情報社会と文字列検索の重要性

私たちが日々触れるデジタル情報のほとんどは、文字列として表現されています。電子メールの本文、ウェブサイトのコンテンツ、ドキュメントファイル、プログラムのソースコード、データベースのエントリ、さらには生物のDNA配列まで、すべては文字の並び、すなわち文字列です。

これらの膨大な文字列データの中から、特定のキーワードやパターンを見つけ出す「文字列検索」は、情報処理における最も基本的な操作の一つです。テキストエディタでの単語検索、インターネット検索エンジンのキーワード検索、アンチウイルスソフトによるマルウェアパターンの検出、遺伝子研究における特定の配列の発見など、文字列検索は私たちのデジタルライフを支える不可欠な技術です。

しかし、テキストの量が Explosion 的に増加するにつれて、効率の悪い検索方法では処理に膨大な時間がかかってしまいます。例えば、テラバイト級のログデータから特定の IP アドレスやエラーメッセージを検索する場合、あるいは全ヒトゲノム配列（約30億塩基対）から特定の遺伝子配列を探す場合など、検索アルゴリズムのわずかな性能差が、結果が得られるまでの時間に劇的な違いをもたらします。

そこで重要となるのが、高速かつ効率的な文字列検索アルゴリズムです。ブルートフォース（力任せ）な手法では非効率となるような大規模なデータに対しても、高速にパターンを見つけ出すための様々なアルゴリズムが研究・開発されてきました。その中でも特に有名な、そして理論的に非常に洗練されたアルゴリズムの一つが、KMPアルゴリズムです。

KMPアルゴリズムは、1977年に Donald Knuth、James Morris、Vaughan Pratt という3人の研究者によって発表されました。彼らはそれぞれ独立に同じアルゴリズムを発見し、その頭文字を取って KMPアルゴリズムと呼ばれています。このアルゴリズムは、テキストの長さ $n$ とパターンの長さ $m$ に対して、計算時間が $O(n+m)$ という線形時間で済むという、非常に優れた特徴を持っています。

本記事では、まず文字列検索の最も基本的な手法である「素朴なアルゴリズム」を紹介し、その性能的な限界を明らかにします。次に、KMPアルゴリズムがどのようにこの限界を克服するのか、その核心となるアイデアである「ジャンプ」のメカニズムに迫ります。そして、そのジャンプを可能にする「失敗関数（Failure Function）」の概念、その計算方法、そして失敗関数を用いた KMP 検索アルゴリズム本体の具体的な手順を、豊富な例を交えながら詳細に解説します。最終的に、KMPアルゴリズムの利点・欠点、そして現代社会における応用例にも触れ、その重要性を再確認します。

素朴な（ナイーブな）文字列検索アルゴリズム：最も単純だが非効率な方法

KMPアルゴリズムの優位性を理解するためには、まず最も直感的で簡単な文字列検索アルゴリズムである「素朴なアルゴリズム（Naive Algorithm）」の仕組みと限界を知ることが役立ちます。これは、コンピュータの初心者でも容易に思いつくであろう方法であり、多くのプログラミング言語に標準で組み込まれている文字列検索関数も、単純なケースではこのアルゴリズムに近い動作をすることがあります。

アルゴリズムの仕組み

素朴なアルゴリズムは、パターン文字列をテキスト文字列の先頭から順に、1文字ずつ右にずらしながら比較を行っていく方法です。

検索対象のテキスト文字列を $T$、その文字数を $n$ とします。検索したいパターン文字列を $P$、その文字数を $m$ とします。通常、$m \le n$ です。

アルゴリズムの手順は以下の通りです。

テキスト $T$ の中で、パターン $P$ の開始位置となりうる場所を順番に試していきます。最初の候補位置はテキストのインデックス 0 です。次の候補位置はインデックス 1、その次はインデックス 2、… と、テキストのインデックス $i$ を 0 から $n-m$ まで 1 ずつ増やしながら、試していきます。なぜ $n-m$ までかというと、テキストの末尾から $m$ 文字分の領域がない位置 (i > n-m) には、もはや長さ $m$ のパターンを完全に配置することが不可能だからです。
テキストの現在の候補開始位置 $i$ に対して、パターン $P$ の最初の文字 $P[0]$ から最後の文字 $P[m-1]$ までの $m$ 文字と、テキストの $T[i]$ から $T[i+m-1]$ までの $m$ 文字を、1文字ずつ比較します。
パターンの $j$ 番目の文字 $P[j]$ と、テキストの対応する位置 $T[i+j]$ を比較します。ここで、$j$ は 0 から $m-1$ まで動きます。
比較の結果：
- もしすべての $j$ について $P[j]$ と $T[i+j]$ が一致した場合、パターン $P$ がテキスト $T$ のインデックス $i$ から始まる位置で見つかったと判断し、その位置（$i$）を報告します。
- 比較の途中で一つでも $P[j]$ と $T[i+j]$ が一致しなかった場合（ミスマッチ）、その位置 $i$ からのパターンマッチングは失敗と判断します。このとき、内側の比較ループは中断され、外側のループに戻り、テキストにおけるパターンの候補開始位置を i+1 に一つずらして、ステップ 2 から比較をやり直します。
テキストにおけるパターンの候補開始位置 $i$ が $n-m$ に達し、その位置での比較も終了したら、検索は終了です。もし途中でパターンが見つかっていれば報告されています。テキストの最後までパターンが見つからなければ、その旨を報告します。

具体例で見る素朴なアルゴリズムの動き

テキスト $T = \text{“ABABABCABABABCABABABC”}$ ($n=21$)
パターン $P = \text{“ABABABC”}$ ($m=7$)

$i = 0$: テキストのインデックス 0 からパターンを配置。
$T[0..6]$ vs $P[0..6]$
A vs A (マッチ)
B vs B (マッチ)
A vs A (マッチ)
B vs B (マッチ)
A vs A (マッチ)
B vs B (マッチ)
C vs C (マッチ)
すべての文字が一致。パターンがテキストのインデックス 0 で見つかりました。

ここではパターンが最初に見つかったら終了とします。もしすべての出現箇所を探すなら、i を $1$ に進めて検索を続行します。

別の例で、ミスマッチが発生する場合を見てみましょう。
テキスト $T = \text{“ABC ABCDAB ABCDABCDABDE”}$ ($n=23$)
パターン $P = \text{“ABCDABD”}$ ($m=7$)

$i = 0$: $T[0..6]$ (“ABC ABC”) vs $P[0..6]$ (“ABCDABD”)
$T[0]$ vs $P[0]$ (A vs A) マッチ
$T[1]$ vs $P[1]$ (B vs B) マッチ
$T[2]$ vs $P[2]$ (C vs C) マッチ
$T[3]$ vs $P[3]$ ( vs D) ミスマッチ！
この位置での比較を中断。テキストの開始位置を $i=1$ にずらします。比較回数：4回。
$i = 1$: $T[1..7]$ (“BC ABCD”) vs $P[0..6]$ (“ABCDABD”)
$T[1]$ vs $P[0]$ (B vs A) ミスマッチ！
この位置での比較を中断。テキストの開始位置を $i=2$ にずらします。比較回数：1回。
$i = 2$: $T[2..8]$ (“C ABCD”) vs $P[0..6]$ (“ABCDABD”)
$T[2]$ vs $P[0]$ (C vs A) ミスマッチ！
$i=3$ にずらす。比較回数：1回。
$i = 3$: $T[3..9]$ (” ABCDAB”) vs $P[0..6]$ (“ABCDABD”)
$T[3]$ vs $P[0]$ ( vs A) ミスマッチ！
$i=4$ にずらす。比較回数：1回。
$i = 4$: $T[4..10]$ (“ABCDAB “) vs $P[0..6]$ (“ABCDABD”)
$T[4]$ vs $P[0]$ (A vs A) マッチ
$T[5]$ vs $P[1]$ (B vs B) マッチ
$T[6]$ vs $P[2]$ (C vs C) マッチ
$T[7]$ vs $P[3]$ (D vs D) マッチ
$T[8]$ vs $P[4]$ (A vs A) マッチ
$T[9]$ vs $P[5]$ (B vs B) マッチ
$T[10]$ vs $P[6]$ ( vs D) ミスマッチ！
この位置での比較を中断。テキストの開始位置を $i=5$ にずらします。比較回数：7回。

…このように、ミスマッチが発生するたびにパターンをたった1文字だけずらし、テキストの次の位置からパターンの先頭文字と比較をやり直す、という処理を繰り返します。

計算量（時間計算量）の解析

素朴なアルゴリズムの時間計算量は、最悪の場合どのようになるでしょうか？

外側のループは、パターンをずらす開始位置 $i$ を 0 から $n-m$ まで試します。これは合計 $n-m+1$ 回繰り返されます。
内側のループは、各開始位置 $i$ において、テキストとパターンの文字を比較します。この比較は、最大でパターンの長さ $m$ 回行われます（パターン全体が一致する場合、または最後の文字でミスマッチする場合）。

最悪のケースは、パターンのほぼ全体が一致するが、最後の文字で毎回ミスマッチが発生する場合です。
例えば、テキスト $T = \text{“AAAA…A”}$ （$n$ 個の A）とパターン $P = \text{“AAAA…AB”}$ （$m-1$ 個の A の後に B）のような場合です。

$i=0$: $T[0..m-1]$ vs $P[0..m-1]$. $T[0]$ と $P[0]$ から順に比較し、$m-1$ 文字目の A までマッチしますが、$T[m-1]$ (A) と $P[m-1]$ (B) でミスマッチが発生します。比較回数 $m$ 回。パターンを $i=1$ にずらす。
$i=1$: $T[1..m]$ vs $P[0..m-1]$. $T[1]$ と $P[0]$ から順に比較し、$m-1$ 文字目の A までマッチしますが、$T[m]$ (A) と $P[m-1]$ (B) でミスマッチが発生します。比較回数 $m$ 回。パターンを $i=2$ にずらす。
…
$i=n-m$: $T[n-m..n-1]$ vs $P[0..m-1]$. $T[n-m]$ と $P[0]$ から順に比較し、$m-1$ 文字目の A までマッチしますが、$T[n-1]$ (A) と $P[m-1]$ (B) でミスマッチが発生します。比較回数 $m$ 回。

この最悪ケースでは、パターンの開始位置 $i$ を $0$ から $n-m$ まで試す各ステップで、ほぼ $m$ 回の比較が発生します。合計の比較回数は約 $(n-m+1) \times m$ 回となります。
したがって、素朴なアルゴリズムの最悪時間計算量は $O((n-m+1)m)$ であり、通常は $O(nm)$ と簡略化されます。

非効率な点、問題点

$O(nm)$ という計算量は、例えば $n$ が 100 万、$m$ が 1000 の場合、$10^{6} \times 10^{3} = 10^{9}$ という非常に大きな比較回数になる可能性があります。これは、大規模なテキスト検索においては実用的ではありません。

素朴なアルゴリズムの非効率性の根本原因は、ミスマッチが発生した際に、既に一致していた部分文字列に関する情報を全く活用しない点にあります。上記の例 $T = \text{“ABC ABCDAB ABCDABCDABDE”}$, $P = \text{“ABCDABD”}$ の $i=4$ のケースを思い出してください。

$i=4$ で、テキストの $T[4..10]$ （”ABCDAB “）とパターンの $P[0..6]$ （”ABCDABD”）を比較し、$T[10]$ と $P[6]$ でミスマッチが発生しました。しかし、このミスマッチが発生するまでに、$P[0..5]$ （”ABCDAB”）がテキストの $T[4..9]$ （”ABCDAB”）と完全に一致していることは既に確認できていました。

素朴なアルゴリズムはミスマッチの後、パターンを1文字だけずらして $i=5$ に進み、$T[5]$ と $P[0]$ を比較し始めます。しかし、よく考えてみてください。T[4..9] が “ABCDAB” であることから、テキストのインデックス 5 から始まる文字列は “BCDA…” となります。パターン $P$ は “ABCDABD” であり、’A’ で始まります。したがって、$T[5]$ からパターンが始まる可能性は全くありません。同様に、$T[6]$, $T[7]$ からパターンが始まる可能性もありません（それぞれ ‘C’, ‘D’ で始まるため）。

T[4..9] で “ABCDAB” という文字列が既にマッチしているという事実を知っていれば、次にパターンが始まる可能性があるのは、この “ABCDAB” という部分文字列の接尾辞が、パターン $P$ の接頭辞と一致しているような位置だけです。

“ABCDAB” の接尾辞は “B”, “AB”, “DAB”, “CDAB”, “BCDAB”, “ABCDAB” です（空文字列を除く）。
パターン $P = \text{“ABCDABD”}$ の接頭辞は “A”, “AB”, “ABC”, “ABCD”, “ABCDA”, “ABCDAB”, “ABCDABD” です（空文字列を除く）。

これらの接尾辞と接頭辞を比較すると、「AB」という文字列が一致しています。この「AB」は “ABCDAB” の長さ 2 の接尾辞であり、パターン $P$ の長さ 2 の接頭辞 “AB” と一致しています。

つまり、T[4..9] の末尾2文字 “AB” は、パターンの先頭2文字 “AB” と一致しています。したがって、パターン全体を、この一致する2文字が重なるようにずらすことができます。具体的には、T[8..9] の “AB” が、新しい位置でのパターンの先頭 P[0..1] “AB” と一致するようにずらします。これにより、パターンの新しい開始位置はテキストのインデックス 8 となります。

素朴なアルゴリズムは $i=5$ から1文字ずつ進みますが、KMPアルゴリズムはこの知識を利用して、ミスマッチが発生した $i=4$ の位置から一気に $i=8$ の位置までパターンをジャンプさせることができるのです。これにより、間の $i=5, 6, 7$ での無駄な比較を省くことができます。

KMPアルゴリズムの核心は、この「既に一致した部分文字列の構造を利用して、次にパターンが始まる可能性のある位置までパターンを一気にジャンプさせる」という考え方です。このジャンプ量を事前に計算しておくのが「失敗関数」です。

KMPアルゴリズムの核心：ジャンプと失敗関数（π配列 / LPS配列）

KMPアルゴリズム（Knuth-Morris-Pratt Algorithm）は、素朴なアルゴリズムの弱点を克服し、ミスマッチが発生したときにパターンを効率的にずらすことによって、線形時間での検索を実現します。その鍵となるのが、パターンの内部構造を分析して得られる情報である「失敗関数（Failure Function）」です。失敗関数は、他の文献では「境界配列（Border Array）」や「接頭辞関数（Prefix Function）」、「LPS配列（Longest Proper Prefix which is also a Suffix）」などとも呼ばれます。本記事では「失敗関数」という呼称を中心に用います。

失敗関数（π配列）の定義

長さ $m$ のパターン文字列 $P = P[0]P[1]…P[m-1]$ に対して、失敗関数 $\pi$ は長さ $m$ の配列 $\pi[0], \pi[1], …, \pi[m-1]$ として定義されます。

$\pi[i]$ の値は、パターン $P$ の先頭 $i+1$ 文字からなる部分文字列 $P[0…i]$ において、

「自身の真の接頭辞」と「自身の真の接尾辞」が一致する最長の文字列の長さ

を意味します。

「真の接頭辞（Proper Prefix）」とは、文字列自身の全体を含まない接頭辞のことです。例えば、文字列 “ABC” の接頭辞は “”, “A”, “AB”, “ABC” ですが、真の接頭辞は “”, “A”, “AB” です。
同様に、「真の接尾辞（Proper Suffix）」とは、文字列自身の全体を含まない接尾辞のことです。”ABC” の接尾辞は “”, “C”, “BC”, “ABC” ですが、真の接尾辞は “”, “C”, “BC” です。

失敗関数 $\pi[i]$ の値は、パターン $P[0…i]$ における、真の接頭辞かつ真の接尾辞である最長の文字列の長さを教えてくれます。

例：パターン $P = \text{“ABABABC”}$ ($m=7$)

$i=0$: 部分文字列 $P[0]$ (“A”)。真の接頭辞: “”, 真の接尾辞: “”。一致する最長: “”。長さ 0。$\pi[0] = 0$。
$i=1$: 部分文字列 $P[0..1]$ (“AB”)。真の接頭辞: “”, “A”。真の接尾辞: “”, “B”。一致する最長: “”。長さ 0。$\pi[1] = 0$。
$i=2$: 部分文字列 $P[0..2]$ (“ABA”)。真の接頭辞: “”, “A”, “AB”。真の接尾辞: “”, “A”, “BA”。一致する最長: “A”。長さ 1。$\pi[2] = 1$。
$i=3$: 部分文字列 $P[0..3]$ (“ABAB”)。真の接頭辞: “”, “A”, “AB”, “ABA”。真の接尾辞: “”, “B”, “AB”, “BAB”。一致する最長: “AB”。長さ 2。$\pi[3] = 2$。
$i=4$: 部分文字列 $P[0..4]$ (“ABABA”)。真の接頭辞: “”, “A”, “AB”, “ABA”, “ABAB”。真の接尾辞: “”, “A”, “BA”, “ABA”, “BABA”。一致する最長: “ABA”。長さ 3。$\pi[4] = 3$。
$i=5$: 部分文字列 $P[0..5]$ (“ABABAB”)。真の接頭辞: “”, “A”, “AB”, “ABA”, “ABAB”, “ABABA”。真の接尾辞: “”, “B”, “AB”, “BAB”, “ABAB”, “BABAB”。一致する最長: “ABAB”。長さ 4。$\pi[5] = 4$。
$i=6$: 部分文字列 $P[0..6]$ (“ABABABC”)。真の接頭辞: $P[0..5]$ まで。真の接尾辞: $P[1..6]$ まで。一致する最長: “”。長さ 0。$\pi[6] = 0$。

したがって、パターン $P = \text{“ABABABC”}$ の失敗関数 $\pi$ は $\text{[0, 0, 1, 2, 3, 4, 0]}$ となります。

失敗関数がジャンプに使える理由

KMPアルゴリズムでは、テキスト $T$ とパターン $P$ を比較している際に、テキストのインデックス $i$ とパターンのインデックス $j$ でミスマッチが発生したとします。これは、これまでの $j$ 回の比較、すなわち $T[i-j…i-1]$ と $P[0…j-1]$ が一致している状態で、$T[i]$ と $P[j]$ が一致しなかったということです。

ミスマッチが発生したということは、テキストの現在の位置 $T[i]$ が、パターン $P$ の $j$ 番目の文字 $P[j]$ と異なるということです。つまり、パターン全体 $P$ はテキストの $T[i-j]$ から始まる位置には出現しません。

では、次にパターンが出現する可能性があるのはどこでしょうか？ KMP は、既に一致している部分 $T[i-j…i-1]$ に注目します。この部分はパターン $P$ の接頭辞 $P[0…j-1]$ と一致しています。次にパターンが始まる可能性のある位置は、この一致している部分 $T[i-j…i-1]$ の接尾辞が、パターン $P$ の接頭辞として一致するような位置です。

失敗関数 $\pi[j-1]$ は、パターン $P[0…j-1]$ の最長の真の接頭辞かつ真の接尾辞の長さを示しています。この長さを $k = \pi[j-1]$ とすると、これは $P[0…k-1]$ という接頭辞が $P[j-k…j-1]$ という接尾辞と一致していることを意味します。そして、既に $P[j-k…j-1]$ はテキストの $T[i-k…i-1]$ と一致していることが分かっています（なぜなら $P[0…j-1]$ が $T[i-j…i-1]$ と一致していたからです）。

つまり、ミスマッチが発生した位置 $i$ において、パターンを新しい開始位置にずらした後、その新しい開始位置からパターンの先頭 $k = \pi[j-1]$ 文字が、テキストの $T[i-k…i-1]$ と一致していることが保証されているのです。したがって、新しい位置での比較は、パターンの $k$ 番目の文字 $P[k]$ とテキストの $i$ 番目の文字 $T[i]$ から始めれば良いということになります。

素朴なアルゴリズムはミスマッチ時にパターンを1文字ずつずらしていましたが、KMP は失敗関数 $\pi[j-1]$ の値を利用して、パターンのインデックス $j$ を $k = \pi[j-1]$ に一気に戻すことで、パターン全体を $j-k$ 文字分、効率的に右にずらすことができるのです。このとき、テキストのインデックス $i$ はそのまま維持されるか、または先に進むだけです（戻ることはありません）。これにより、無駄な比較、特に既に一致が確認されている部分の再比較を省くことができます。

失敗関数（π配列）の計算方法

失敗関数 $\pi$ は KMP アルゴリズムの鍵であり、その値は検索を開始する前にパターン $P$ だけを見て計算されます。この計算プロセス自体も効率的に、線形時間 $O(m)$ で行うことができます。失敗関数計算アルゴリズムは、パターンマッチングのアルゴリズムと構造が非常に似ており、パターンを自分自身に対してマッチングさせるようなイメージです。

アルゴリズムの仕組み

長さ $m$ のパターン $P$ に対して、長さ $m$ の配列 $\pi$ を計算します。

$\pi[0]$ は常に 0 に初期化します。これは、長さ 1 の部分文字列 $P[0]$ には、真の接頭辞かつ真の接尾辞となる空でない部分文字列が存在しないためです。
変数 length を用意し、現在の部分文字列 $P[0…i]$ における「真の接頭辞かつ真の接尾辞である最長の長さ」を保持します。初期値は 0 とします (π[0] の計算結果に基づきます)。
インデックス $i$ を 1 から $m-1$ まで順番に進め、各 $i$ に対して $\pi[i]$ を計算します。これは、部分文字列 $P[0…i]$ についての情報を計算していることにあたります。
各ステップ $i$ において、$P[i]$（現在の部分文字列の末尾に追加された新しい文字）と $P[length]$（現在までに一致している最長の接頭辞の次の文字）を比較します。
- ケース1: $P[i]$ と $P[length]$ が一致する場合
  これは、現在までに一致している最長の接頭辞／接尾辞を 1 文字伸ばせることを意味します。新しい最長一致長は length + 1 になります。したがって、$\pi[i]$ を length + 1 と設定し、次のステップのために length を length + 1 に更新します。そして $i$ も 1 つ進めます。
- ケース2: $P[i]$ と $P[length]$ が一致しない場合
  これは、現在の length で示される長さの接頭辞／接尾辞の一致を 1 文字伸ばせなかったことを意味します。より短い接頭辞／接尾辞の一致を探す必要があります。このとき、現在一致していた長さ length の接頭辞 $P[0…length-1]$ の中で、次に短い「真の接頭辞かつ真の接尾辞」の長さを $\pi[length-1]$ を見て取得します。そして length を $\pi[length-1]$ の値に更新します。これは、パターンの比較位置を戻すこと（ジャンプ）に相当します。新しい length の値を使って、再び $P[i]$ と $P[length]$ を比較します。この処理を、一致が見つかるか、または length が 0 になるまで繰り返します。
  - もし length が 0 になり、それでも $P[i]$ と $P[0]$ が一致しない場合、部分文字列 $P[0…i]$ には、空でない真の接頭辞かつ真の接尾辞は存在しないということです。この場合、$\pi[i] = 0$ と設定し、$i$ を 1 つ進めます。length は 0 のままです。
  - もし length が 0 になった後で $P[i]$ と $P[0]$ が一致した場合、部分文字列 $P[0…i]$ の最長一致長は 1 になります。この場合、$\pi[i] = 1$ と設定し、length を 1 に更新します。そして $i$ を 1 つ進めます。

このプロセスを $i$ が $m-1$ に達するまで繰り返すと、全ての $\pi[i]$ の値が計算されます。

失敗関数計算の擬似コード

“`python
function compute_failure_function(P, m):
pi = array of size m # Create an array of size m to store failure function values
pi[0] = 0 # The value for the first character P[0] is always 0

# length is the length of the previous longest prefix suffix
length = 0

# i is the index for pi[i] and also the index of the character being considered in P
# Start from the second character (index 1) because pi[0] is already set
i = 1

while i < m:
    # Compare the current character P[i] with the character at P[length]
    # P[length] is the character that would follow the current "longest prefix suffix"
    if P[i] == P[length]:
        # If they match, we extend the longest prefix suffix by 1
        length = length + 1
        pi[i] = length
        i = i + 1
    else:
        # If they do not match (mismatch)
        # Check if we are not at the beginning of the pattern (length > 0)
        if length != 0:
            # This is tricky. We look up the previous length's failure value.
            # We don't increment i here. We re-compare P[i] with P[length']
            # where length' is pi[length - 1].
            # This is essentially simulating a mismatch in the pattern itself.
            length = pi[length - 1]
        else:
            # If length is 0, it means P[0] != P[i].
            # The longest prefix suffix for P[0...i] is the empty string.
            pi[i] = 0
            i = i + 1

return pi

“`

具体例による失敗関数計算

パターン $P = \text{“ABCDABD”}$ ($m=7$)

pi 配列 (サイズ 7) を用意。pi[0] = 0。
length = 0, i = 1。

i	P[i]	length	P[length]	P[i] == P[length]?	Action	New length	New i	pi
–	–	0	–	–	Initialize pi[0] = 0	0	1	[0, ?, ?, ?, ?, ?, ?]
1	‘B’	0	P[0] (‘A’)	No	length = 0? Yes. pi[1] = 0, i++	0	2	[0, 0, ?, ?, ?, ?, ?]
2	‘C’	0	P[0] (‘A’)	No	length = 0? Yes. pi[2] = 0, i++	0	3	[0, 0, 0, ?, ?, ?, ?]
3	‘D’	0	P[0] (‘A’)	No	length = 0? Yes. pi[3] = 0, i++	0	4	[0, 0, 0, 0, ?, ?, ?]
4	‘A’	0	P[0] (‘A’)	Yes	length++, pi[4] = length, i++	1	5	[0, 0, 0, 0, 1, ?, ?]
5	‘B’	1	P[1] (‘B’)	Yes	length++, pi[5] = length, i++	2	6	[0, 0, 0, 0, 1, 2, ?]
6	‘D’	2	P[2] (‘C’)	No	length = 0? No. length = pi[length-1] (pi[1])	0	6	[0, 0, 0, 0, 1, 2, ?]
6	‘D’	0	P[0] (‘A’)	No	length = 0? Yes. pi[6] = 0, i++	0	7	[0, 0, 0, 0, 1, 2, 0]

$i$ が $m$ (7) に達したのでループ終了。
失敗関数 $\pi = [0, 0, 0, 0, 1, 2, 0]$ と計算されました。

計算量の解析

失敗関数計算アルゴリズムの時間計算量は $O(m)$ です。

擬似コードを見ると、外側の while ループは i < m の間続きます。i は P[i] == P[length] のケース、または P[i] != P[length] かつ length == 0 のケースでインクリメントされます。つまり、i は常に増加するか維持されるだけで、減少することはありません。そして i は最大で m-1 まで増加します。これは i が高々 $m$ 回インクリメントされることを意味します。

P[i] != P[length] かつ length != 0 のケースでは、i はインクリメントされず、length = pi[length - 1] によって length の値が小さくなります。length の値は常に非負であり、最大で $m-1$ の値をとります。length が減少する回数は、それが増加する回数によって制限されます。length は P[i] == P[length] のケースでのみ増加し、1 回の増加につき高々 1 増加します。したがって、length の総増加量は高々 $m-1$ です。length が減少する際には常に 1 以上減少するため（$\pi[k] < k+1$ なので $\pi[length-1] < length$）、length が減少する合計回数は、その総増加量を超えることはありません。

したがって、i のインクリメントによるステップ数と、length の減少によるステップ数を合わせても、全体のステップ数は $O(m)$ に収まります。

空間計算量は、失敗関数 $\pi$ を格納するために $O(m)$ が必要です。

失敗関数の計算は、KMP検索を行う前に一度だけ実行される前処理です。

KMP検索アルゴリズム本体

失敗関数 $\pi$ の計算が終われば、いよいよその情報を使ってテキスト $T$ からパターン $P$ を検索します。KMP検索アルゴリズムは、テキストとパターンの両方を一方向（通常は左から右）に走査していきます。

アルゴリズムの仕組み

テキスト文字列 $T$（長さ $n$）、パターン文字列 $P$（長さ $m$）、そして事前に計算された失敗関数 $\pi$（長さ $m$）を入力とします。

テキストの現在の比較位置を指すインデックスを i、パターンの現在の比較位置を指すインデックスを j とします。j はまた、テキストの現在の位置 $i$ から遡って $i-j$ の位置から始まるテキスト部分が、パターンの先頭 $j$ 文字 $P[0…j-1]$ と一致していることを示しています。

アルゴリズムの手順は以下の通りです。

テキストのインデックス i を 0 に、パターンのインデックス j を 0 に初期化します。i はテキストの走査位置、j はパターンの中でテキストの T[i] と比較している文字のインデックスです。
テキストの最後まで (i < n) ループを続けます。
現在のテキスト文字 T[i] と、パターンの現在の比較位置の文字 P[j] を比較します。
- ケース1: T[i] と P[j] が一致する場合
  現在までに一致していた部分を 1 文字伸ばすことに成功しました。テキストとパターンの両方のインデックスを 1 つ進めます (i++, j++)。
  - もし j がパターンの長さ m に達した場合 (j == m)、これはパターン全体がテキストのインデックス $i-m$ から始まる位置で完全に一致したことを意味します。パターンが見つかった位置 $i-m$ を報告します。もしテキスト中にパターンが複数回出現する可能性を全て探す場合、検索を継続する必要があります。パターン全体が一致した P[0...m-1] という文字列に対して、次に比較を再開すべきパターンの位置は、失敗関数 $\pi[m-1]$ の値によって与えられます。すなわち、パターンのインデックス j を $\pi[m-1]$ に更新します。これにより、パターン全体が $m-\pi[m-1]$ 文字分右にスライドしたことになり、新しい開始位置からパターンの先頭 $\pi[m-1]$ 文字はテキストの既知の一致部分と重なっていることが利用されます。テキストのインデックス i はそのまま維持し、新しい j の値で比較を続けます。
- ケース2: T[i] と P[j] が一致しない場合 (ミスマッチ)
  これは、現在の位置でのパターンマッチングが失敗したことを意味します。テキストのインデックス i は戻しません。テキストの T[i] と比較を続けるために、パターンのインデックス j だけを更新して、パターンを右にスライドさせます。
  - もし j > 0 (つまり、パターンの先頭文字以外でミスマッチが発生した) なら、これは $P[0…j-1]$ がテキストのある部分と一致していたにも関わらず、$P[j]$ でミスマッチが発生したということです。失敗関数 $\pi[j-1]$ の値を利用して、次にテキストの T[i] と比較すべきパターンの文字のインデックスを決定します。新しいパターンの比較位置は $\pi[j-1]$ です。j を $\pi[j-1]$ に更新します。テキストのインデックス i はそのまま維持し、新しい j の値で比較を再開します。これにより、パターンは $j – \pi[j-1]$ 文字分右にスライドしたことになります。
  - もし j == 0$ (つまり、パターンの先頭文字 $P[0]$ とテキストの $T[i]$ でミスマッチが発生した) なら、これはテキストの現在の位置 $i$ からはパターンの先頭文字すら一致しないということです。失敗関数は使えません（$\pi[-1]$ は定義されない）。この場合、パターンを 1 文字ずらして、テキストの次の文字 $T[i+1]$ からパターンの先頭 $P[0]$ と比較をやり直すしかありません。テキストのインデックスiを 1 つ進めて (i++)、パターンのインデックスj` は 0 のままにします。
テキストのインデックス i が $n$ に達したら、ループを終了します。

KMP検索アルゴリズムの擬似コード

“`python
function kmp_search(T, n, P, m, pi):
i = 0 # index for text T (0 to n-1)
j = 0 # index for pattern P (0 to m-1)

while i < n:
    # Case 1: Characters match
    if P[j] == T[i]:
        i = i + 1
        j = j + 1

    # Case 2: Pattern found
    if j == m:
        # Pattern found at index i - j in text T
        print "Pattern found at index", i - j
        # To find the next occurrence, simulate a mismatch at the end of P
        # The next character to compare in the pattern will be at index pi[j-1]
        # Text index i remains where it is (the character after the match)
        j = pi[j - 1]

    # Case 3: Mismatch after one or more characters have matched (j > 0)
    # Note: This 'else if' triggers if P[j] != T[i] AND j < m AND i < n (due to outer loop)
    elif i < n and P[j] != T[i]:
        # If j is not 0, it means we had a partial match P[0...j-1] that failed at P[j].
        # Use the failure function to determine the next potential match start within the text we've already seen.
        # The character T[i] which caused the mismatch will now be compared with P[pi[j-1]].
        if j != 0:
            j = pi[j - 1]
        # Case 4: Mismatch at the beginning of the pattern (j == 0)
        else: # j == 0 and P[0] != T[i]
            # If the first character of the pattern doesn't match T[i],
            # move to the next character in the text (i+1) and try matching P[0] again.
            i = i + 1

`` 擬似コードの構造は、パターン発見時の処理とミスマッチ時の処理を明確にするために、マッチ判定の次にパターン発見判定、そしてミスマッチ判定という順序で記述することが多いです。while i < nループがテキストの最後まで走査することを保証します。ミスマッチ時のi < nのチェックは、理論上はwhile` ループの条件で保証されますが、念のため明示することも多いです。

具体例によるKMP検索の実行

テキスト $T = \text{“ABC ABCDAB ABCDABCDABDE”}$ ($n=23$)
パターン $P = \text{“ABCDABD”}$ ($m=7$)
失敗関数 $\pi = [0, 0, 0, 0, 1, 2, 0]$ （前に計算したもの）

検索開始: i = 0, j = 0

i=0, j=0: T[0]==’A’, P[0]==’A’. マッチ. i=1, j=1.
i=1, j=1: T[1]==’B’, P[1]==’B’. マッチ. i=2, j=2.
i=2, j=2: T[2]==’C’, P[2]==’C’. マッチ. i=3, j=3.
i=3, j=3: T[3]==’ ‘, P[3]==’D’. ミスマッチ. j != 0 (3 > 0). j = pi[j-1] = pi[2] = 0. i はそのまま (3).
- パターンが $3-0=3$ 文字分右にずれたイメージ。テキストの $T[3]$ は新しいパターンの先頭 $P[0]$ と比較される。
i=3, j=0: T[3]==’ ‘, P[0]==’A’. ミスマッチ. j == 0. i++ (i=4). j は 0 のまま.
- テキスト位置を進めて、新しいテキスト文字 $T[4]$ からパターンの先頭 $P[0]$ と比較開始。
i=4, j=0: T[4]==’A’, P[0]==’A’. マッチ. i=5, j=1.
i=5, j=1: T[5]==’B’, P[1]==’B’. マッチ. i=6, j=2.
i=6, j=2: T[6]==’C’, P[2]==’C’. マッチ. i=7, j=3.
i=7, j=3: T[7]==’D’, P[3]==’D’. マッチ. i=8, j=4.
i=8, j=4: T[8]==’A’, P[4]==’A’. マッチ. i=9, j=5.
i=9, j=5: T[9]==’B’, P[5]==’B’. マッチ. i=10, j=6.
i=10, j=6: T[10]==’ ‘, P[6]==’D’. ミスマッチ. j != 0 (6 > 0). j = pi[j-1] = pi[5] = 2. i はそのまま (10).
- パターンが $6-2=4$ 文字分右にずれたイメージ。テキストの $T[10]$ は新しいパターンの $P[2]$ と比較される。これは、$T[4..9]$ と $P[0..5]$ が一致していたことから、$T[8..9]$ は $P[4..5]$ と一致しており、さらに $P[4..5]$ は $P[0..1]$ と一致していることを利用している（$\pi[5]=2$ だから）。だから、パターンをずらした後、$T[8..9]$ は新しいパターンの $P[0..1]$ と一致していると分かり、比較は $T[10]$ と $P[2]$ から再開できる。
i=10, j=2: T[10]==’ ‘, P[2]==’C’. ミスマッチ. j != 0 (2 > 0). j = pi[j-1] = pi[1] = 0. i はそのまま (10).
- パターンが $2-0=2$ 文字分右にずれたイメージ。テキストの $T[10]$ は新しいパターンの $P[0]$ と比較される。
i=10, j=0: T[10]==’ ‘, P[0]==’A’. ミスマッチ. j == 0$.i++(i=11).j` は 0 のまま.
- テキスト位置を進めて、新しいテキスト文字 $T[11]$ からパターンの先頭 $P[0]$ と比較開始。
i=11, j=0: T[11]==’A’, P[0]==’A’. マッチ. i=12, j=1.
i=12, j=1: T[12]==’B’, P[1]==’B’. マッチ. i=13, j=2.
i=13, j=2: T[13]==’C’, P[2]==’C’. マッチ. i=14, j=3.
i=14, j=3: T[14]==’D’, P[3]==’D’. マッチ. i=15, j=4.
i=15, j=4: T[15]==’A’, P[4]==’A’. マッチ. i=16, j=5.
i=16, j=5: T[16]==’B’, P[5]==’B’. マッチ. i=17, j=6.
i=17, j=6: T[17]==’D’, P[6]==’D’. マッチ. i=18, j=7.
j == m (7 == 7). パターン発見！位置は $i – j = 18 – 7 = 11$.
次の出現を探すため、j = pi[j-1] = pi[6] = 0. i はそのまま (18).
- パターン全体が一致した $T[11..17]$ (“ABCDABD”) に対して、次にパターンが出現する可能性のある位置を探索。パターン全体で真の接頭辞かつ真の接尾辞となる最長は長さ 0 ($\pi[6]=0$) なので、パターン全体がマッチした部分との重なりを利用してスキップできる既知の一致はない。次の探索はパターン先頭 $P[0]$ から開始する。
i=18, j=0: T[18]==’A’, P[0]==’A’. マッチ. i=19, j=1.
i=19, j=1: T[19]==’B’, P[1]==’B’. マッチ. i=20, j=2.
i=20, j=2: T[20]==’D’, P[2]==’C’. ミスマッチ. j != 0 (2 > 0). j = pi[j-1] = pi[1] = 0. i はそのまま (20).
- パターンが $2-0=2$ 文字分右にずれたイメージ。テキストの $T[20]$ は新しいパターンの $P[0]$ と比較される。
i=20, j=0: T[20]==’D’, P[0]==’A’. ミスマッチ. j == 0. i++ (i=21). j は 0 のまま.
i=21, j=0: T[21]==’E’, P[0]==’A’. ミスマッチ. j == 0$.i++(i=22).j` は 0 のまま.
i=22, j=0: T[22]==’ ‘, P[0]==’A’. ミスマッチ. j == 0$.i++(i=23).j` は 0 のまま.
i=23: i < n (23 < 23) が偽。ループ終了。

検索終了。パターンはテキストのインデックス 11 で見つかりました。素朴なアルゴリズムと比べて、多くの無駄な比較ステップがスキップされていることが分かります。特に、ミスマッチ時にテキストインデックス i が戻らない点が効率化に寄与しています。

計算量（時間計算量）の解析

KMP検索アルゴリズム本体の時間計算量は $O(n)$ です。
全体の時間計算量は、失敗関数の計算 $O(m)$ と検索本体 $O(n)$ を合計して $O(n+m)$ となります。

なぜ検索本体が $O(n)$ なのかをもう少し詳しく見てみます。
KMP アルゴリズムの実行中に、テキストのインデックス $i$ は決して減少しません。マッチした場合 (P[j] == T[i]) は i と j が両方インクリメントされます。ミスマッチして j == 0 の場合 (P[0] != T[i]) は i だけインクリメントされます。ミスマッチして j > 0 の場合 (P[j] != T[i] and j > 0) は i はそのまま維持され、j だけが j = pi[j-1] によって厳密に減少します。

テキストインデックス i は、最大で $n$ までしか進まないので、i がインクリメントされる操作の合計回数は $O(n)$ です。
一方、パターンのインデックス j は、マッチした場合にのみ増加します。各マッチで j は 1 増加し、最大で $m$ まで増加します。したがって、j の総増加量は高々 $O(n)$ です（なぜなら、j が $m$ に達するごとに発見イベントが発生し、j がリセットされるからです。各テキスト文字は最大1回しかパターン文字とマッチしないため、j の総増加量は $n$ を超えません）。
ミスマッチして j > 0 の場合に j は減少します。しかし、j の減少回数は、その前の増加回数によって制限されます。j の総減少量は、その総増加量を超えることはありません。j の総増加量は $O(n)$ であり、j の減少回数も $O(n)$ を超えないことが数学的に証明できます。

したがって、i のインクリメント回数 ($O(n)$)、j の増加回数 ($O(n)$)、そして j の減少回数 ($O(n)$) を合計したものが、アルゴリズムの実行ステップ数に比例します。これにより、KMP検索本体の時間計算量は $O(n)$ となります。

空間計算量は、失敗関数 $\pi$ を格納するための $O(m)$ です。

KMPアルゴリズムの利点と欠点

利点

最適化された時間計算量: O(n+m) という線形時間は、テキスト検索アルゴリズムとして理論的に非常に優れています。テキストサイズが大きくなってもパフォーマンスの劣化が少なく、大規模データ検索に適しています。これは、テキストの各文字が高々定数回しか比較されないことに起因します。
効率的な空間利用: 必要な追加メモリはパターンサイズに依存する O(m) だけであり、テキストサイズには依存しません。これは、メモリが限られている環境や、巨大なテキストを扱う場合に有利です。
オンライン処理: テキストを最初から最後まで一度だけ走査するだけで検索が完了します。これは、テキストがストリームのようにリアルタイムで供給されるような状況（例えばネットワークトラフィックの監視など）で有効です。

欠点

アルゴリズムの複雑さ: 素朴なアルゴリズムと比較すると、失敗関数という概念とその計算方法、そして検索中のジャンプ処理のロジックがやや複雑であり、初学者にとっては理解や正確な実装が難しい場合があります。
パターンの事前処理コスト: 検索を開始する前に、パターンの失敗関数を計算する O(m) の前処理が必要です。もしパターンが頻繁に変更されるようなアプリケーションでは、この前処理のコストが全体のパフォーマンスに影響を与える可能性があります。しかし、一つのパターンを使って複数のテキストを検索する場合や、同じパターンで繰り返し検索を行う場合には、この前処理コストは検索全体の時間に比べて小さくなり、償却されます。

応用例

KMPアルゴリズムは、その効率性からコンピュータサイエンスや様々な分野で幅広く応用されています。

テキストエディタやコードエディタの検索/置換機能: 大容量のファイルを扱う際に、ユーザーが指定した単語やフレーズを高速に探し出したり、置換したりするために利用されます。
コマンドラインツール（例: grep）: UNIX/Linux 環境で広く使われる grep コマンドは、ファイルからパターンに一致する行を検索する強力なツールですが、その高速な動作のために KMP やその発展形、あるいは他の効率的なアルゴリズム（例: Boyer-Moore）が内部的に使われることがあります。
コンパイラとインタープリタ: プログラミング言語のソースコードを解析する際、字句解析（lexer）の段階でキーワード、識別子、演算子などのトークンを認識するためにパターンマッチングが用いられます。
バイオインフォマティクス: DNA や RNA、タンパク質などの生物学的配列データの中から、特定の遺伝子配列や機能ドメインなど、興味のあるパターンを高速に検索するために KMP が使われます。大規模なゲノムデータに対して効率的な検索は不可欠です。
ネットワークセキュリティ（IDS/IPS、アンチウイルス）: ネットワークを流れるパケットやファイルの内容から、既知の攻撃パターンやマルウェアのシグネチャをリアルタイムで検出するために、高速なパターンマッチングが必要です。KMP や Aho-Corasick といったアルゴリズムがこのようなシステムで利用されます。
データ圧縮: データ圧縮アルゴリズムの中には、繰り返し出現するパターンを見つけて効率的に符号化するものがあり、その過程で文字列検索アルゴリズムが応用されることがあります。

まとめ：KMPアルゴリズムの重要性と学習の価値

本記事では、KMPアルゴリズムの理論と実践について、素朴なアルゴリズムとの比較から始め、その核心である失敗関数、そして検索本体の仕組みまでを詳細に解説しました。

素朴なアルゴリズムが持つ、ミスマッチ時の無駄な比較という非効率性を、KMP はパターンの内部構造を分析した失敗関数を利用することで見事に克服します。ミスマッチが発生してもテキストのインデックスを戻さず、パターンの比較位置だけを適切にジャンプさせることで、テキストの各文字に対して行う比較回数を最小限に抑え、全体として線形時間 O(n+m) という極めて高速な文字列検索を実現しています。

失敗関数の計算プロセス自体も、パターンマッチングと似た線形時間アルゴリズムで実行でき、検索の前処理として効率的に完了します。

KMPアルゴリズムは、その優れた時間計算量と空間効率性から、コンピュータサイエンスにおける文字列処理アルゴリズムの代表例として、また多くの実用的なシステムで利用される基盤技術として、非常に重要な位置を占めています。特に、大規模なテキストデータや、リアルタイムでの高速処理が求められる場面では、KMP のような効率的なアルゴリズムの知識が不可欠となります。

確かに、素朴なアルゴリズムに比べるとアルゴリズムの理解には少し複雑さが伴いますが、失敗関数がどのように機能し、それがどのようにジャンプ量を決定するのかという核心部分を掴めば、そのエレガントさと効率性の理由が明確になるはずです。

アルゴリズム学習において、KMP は動的計画法的な考え方（失敗関数の計算）と、巧妙な状態遷移（検索本体の i, j の更新）を組み合わせた良い例であり、他の応用的なアルゴリズムやデータ構造を学ぶ上でも役立つ概念が多く含まれています。

本記事を通じて、KMPアルゴリズムの仕組みと、それがなぜ高速な文字列検索を可能にするのかについて、深い理解を得ていただけたなら幸いです。計算機科学の世界における強力なツールの一つとして、KMPアルゴリズムの知識をぜひ活用してください。

KMPアルゴリズムとは？高速な文字列検索の仕組みを徹底解説

はじめに：なぜ高速な文字列検索が必要なのか？

素朴な（ナイーブな）文字列検索アルゴリズム

アルゴリズムの仕組み

具体例

計算量（時間計算量）の解析

非効率な点、問題点

KMPアルゴリズムの核心：ジャンプ（スキップ）の考え方

KMPのアイデア：ミスマッチからの飛躍

失敗関数（π配列 / LPS配列）とは？

失敗関数（π配列）の計算

失敗関数計算アルゴリズム

失敗関数計算の擬似コード

具体例による失敗関数計算

計算量の解析

KMP検索アルゴリズム本体

アルゴリズムの仕組み

KMP検索アルゴリズムの擬似コード

具体例によるKMP検索

計算量（時間計算量）の解析

KMPアルゴリズムの利点と欠点

利点

欠点

応用例

まとめ

KMPアルゴリズムとは？高速な文字列検索の仕組みを徹底解説

はじめに：情報社会と文字列検索の重要性

素朴な（ナイーブな）文字列検索アルゴリズム：最も単純だが非効率な方法

アルゴリズムの仕組み

具体例で見る素朴なアルゴリズムの動き

計算量（時間計算量）の解析

非効率な点、問題点

KMPアルゴリズムの核心：ジャンプと失敗関数（π配列 / LPS配列）

失敗関数（π配列）の定義

失敗関数がジャンプに使える理由

失敗関数（π配列）の計算方法

アルゴリズムの仕組み

失敗関数計算の擬似コード

具体例による失敗関数計算

計算量の解析

KMP検索アルゴリズム本体

アルゴリズムの仕組み

KMP検索アルゴリズムの擬似コード

具体例によるKMP検索の実行

計算量（時間計算量）の解析

KMPアルゴリズムの利点と欠点

利点

欠点

応用例

まとめ：KMPアルゴリズムの重要性と学習の価値

コメントする 返信をキャンセル

コメントする返信をキャンセル