文字列検索を高速化！KMPアルゴリズムの基本を紹介

はじめに：なぜ文字列検索は速くなければならないのか？

私たちが日常的にコンピュータを使う上で、最も頻繁に行われる操作の一つに「文字列検索」があります。ドキュメントの中から特定のキーワードを探したり、ウェブページの内容を検索したり、プログラムコードの中から特定の関数名を見つけ出したり、データベースから該当する情報を引き出したり。これらすべてが文字列検索、あるいはその派生技術の上に成り立っています。

現代において、扱うデータ量は爆発的に増加しています。巨大なテキストファイル、大規模なコードベース、あるいはインターネット上の膨大な情報から、目的の文字列を瞬時に見つけ出すことは、システムの応答速度やユーザーエクスペリエンスに直結する非常に重要な課題です。もし文字列検索が遅ければ、私たちのデジタルライフはたちまち非効率でストレスフルなものになってしまうでしょう。

例えば、皆さんが毎日利用する検索エンジンの裏側では、世界中のウェブページから関連性の高い情報を瞬時に探し出すために、超高速な文字列検索技術が駆使されています。テキストエディタで数十万行あるファイルの中から特定の単語を探すときも、一瞬で結果が表示されるのが当たり前になっています。これらの快適さは、効率的なアルゴリズムによって支えられているのです。

文字列検索アルゴリズムは、大きく分けて、テキスト（検索対象の長い文字列）の中から、パターン（検索したい短い文字列）が出現する位置を見つけ出すことを目的とします。最も単純な方法から高度なアルゴリズムまで様々な手法が研究されていますが、その中でもKMPアルゴリズム（Knuth-Morris-Pratt algorithm）は、理論的に非常に効率が良いアルゴリズムとして知られており、その洗練された考え方は多くの応用技術の基礎となっています。

本記事では、このKMPアルゴリズムの「基本」に焦点を当て、なぜこのアルゴリズムが高速なのか、その核となる考え方や具体的な仕組みについて、素朴なアルゴリズムと比較しながら詳しく解説していきます。約5000語という十分な量を使って、初心者の方でもKMPアルゴリズムの魅力を理解できるよう、丁寧に掘り下げていきます。

素朴な文字列検索アルゴリズムとその問題点

KMPアルゴリズムの話に入る前に、まずは最も直感的で素朴な文字列検索アルゴリズム、通称「ナイーブ法（Naive Method）」や「力任せ探索（Brute Force Search）」と呼ばれる方法を見てみましょう。この方法がなぜ非効率になることがあるのかを理解することは、KMPアルゴリズムの優位性を知る上で重要です。

ナイーブ法は、テキスト（T）の先頭から順に、パターン（P）と比較していく方法です。
テキストの長さを $n$、パターンの長さを $m$ とします。テキストを $T[0..n-1]$、パターンを $P[0..m-1]$ と表記することにします。

アルゴリズムの基本的な流れは以下のようになります。

テキストの最初の文字 $T[0]$ からパターン $P[0]$ を比較を開始します。テキストにおける現在の比較開始位置を i (0から $n-m$ まで)、パターンにおける現在の比較位置を j (0から $m-1$ まで) とします。最初は i=0, j=0 です。
T[i+j] と P[j] を比較します。
もし一致するなら、パターンの次の文字へと進みます。つまり、j をインクリメントして、T[i+j+1] と P[j+1] を比較します。これを、パターン全体 (j が $m-1$ になるまで) 一致するまで繰り返します。
もし j が $m$ に達したら、パターンがテキストの i の位置から完全に一致したことになります。一致が見つかりました！もしテキスト中に複数回パターンが出現する可能性を探るなら、テキストの比較開始位置 i を一つ進めて (i+1)、再度パターンの最初 (j=0) から比較を再開します。
もし T[i+j] と P[j] が一致しない場合、現在のテキストの比較開始位置 i からはパターンが出現しないことが確定します。この場合、テキストの比較開始位置を一つずらします。つまり、i を i+1 とし、パターンの比較位置 j は最初の0に戻して、テキストの次の位置から再度パターン全体との比較を開始します。
テキストの比較開始位置 i が $n-m$ を超えるまで（つまり、テキストの末尾からパターンを比較するのに十分な文字数がなくなるまで）、このプロセスを繰り返します。

例を見てみましょう。
テキスト T = “ABABDABACD” (n=10)
パターン P = “ABAC” (m=4)

i=0:
- j=0: T[0]==’A’, P[0]==’A’. Match. j=1.
- j=1: T[1]==’B’, P[1]==’B’. Match. j=2.
- j=2: T[2]==’A’, P[2]==’A’. Match. j=3.
- j=3: T[3]==’B’, P[3]==’C’. Mismatch! (T[3] vs P[3])
- 不一致が発生したので、テキストの比較開始位置をずらします。i を 0 から 1 に進め、j を 0 に戻します。
i=1:
- j=0: T[1]==’B’, P[0]==’A’. Mismatch! (T[1] vs P[0])
- 不一致が発生したので、テキストの比較開始位置をずらします。i を 1 から 2 に進め、j を 0 に戻します。
i=2:
- j=0: T[2]==’A’, P[0]==’A’. Match. j=1.
- j=1: T[3]==’B’, P[1]==’B’. Match. j=2.
- j=2: T[4]==’D’, P[2]==’A’. Mismatch! (T[4] vs P[2])
- 不一致が発生したので、テキストの比較開始位置をずらします。i を 2 から 3 に進め、j を 0 に戻します。
i=3: … (省略)
i=4:
- j=0: T[4]==’D’, P[0]==’A’. Mismatch! (T[4] vs P[0])
- i を 4 から 5 に進め、j を 0 に戻します。
i=5:
- j=0: T[5]==’A’, P[0]==’A’. Match. j=1.
- j=1: T[6]==’B’, P[1]==’B’. Match. j=2.
- j=2: T[7]==’A’, P[2]==’A’. Match. j=3.
- j=3: T[8]==’C’, P[3]==’C’. Match! j=4.
- j が 4 (パターンの長さ m) に達しました。パターンがテキストの i=5 の位置から見つかりました (T[5..8] == “ABAC”)。

ナイーブ法は理解しやすく実装も容易ですが、効率の面で大きな問題を抱える場合があります。特に問題となるのは、不一致が発生した際に、テキストの比較位置をほんの少し（1文字）しか進めず、パターンの比較位置を常に最初に戻してしまう点です。

最悪のケースを考えてみましょう。
テキスト T = “AAAAAA…AAAAAB” (n文字)
パターン P = “AAAAB” (m文字)

テキストの先頭からパターンと比較していくと、最後の文字 ‘B’ 以外は全て一致します。
T[0..m-2] と P[0..m-2] は一致し、T[m-1] と P[m-1] で不一致となります。
ナイーブ法では、ここでテキストの比較開始位置を1つずらして T[1] から再比較を開始します。
すると、また T[1..m-1] と P[0..m-2] が一致し、T[m] と P[m-1] で不一致となります。
これを繰り返すと、テキストのほとんど全ての位置 i について、パターンのほぼ全体 (m-1 文字) を比較することになります。
テキストの長さが $n$、パターンの長さが $m$ の場合、最悪のケースでは約 $n \times m$ 回の文字比較が発生する可能性があります。計算量は $O(nm)$ となります。

データ量が少ないうちは問題ありませんが、 $n$ や $m$ が大きくなると、この $O(nm)$ という計算量は致命的な遅さにつながります。特に大量のデータに対して頻繁に検索を行うようなシステムでは、より高速なアルゴリズムが不可欠です。KMPアルゴリズムは、このナイーブ法の問題を解決するために考案された画期的な手法です。

KMPアルゴリズムの誕生背景と基本的なアイデア

KMPアルゴリズムは、ドナルド・クヌース（Donald Knuth）、ジェームズ・モリス（James Morris）、ヴォーン・プラット（Vaughan Pratt）の3氏によって1970年代に独立に考案・発表された文字列検索アルゴリズムです。その名前は3氏の頭文字から取られています。

KMPアルゴリズムがナイーブ法の問題を克服する基本的なアイデアは、以下の2点に集約されます。

不一致が発生した際に、テキストの比較位置を後戻りさせない。 ナイーブ法では、不一致時にテキストのインデックス i をリセットして1つずつずらしていましたが、KMPではテキスト側のインデックス i は常に前進するか、少なくとも後戻りはしません。
不一致が発生した際に、パターンの比較位置を効率的にジャンプさせる。 ここがKMPアルゴリズムの最も重要なポイントです。パターン比較中に不一致が起こったとき、ナイーブ法のように単にパターン全体をずらして最初から比較し直すのではなく、「これまでの比較で分かった情報」を最大限に活用して、パターンを可能な限り大きくシフトさせます。

では、「これまでの比較で分かった情報」とは何でしょうか？ KMPアルゴリズムが着目したのは、パターン自身が持つ「構造」、特に「パターンの一部が、自身の接頭辞（プレフィックス）として出現している」という性質です。

例として、パターン P = “ABABCABAB” を考えてみましょう。
このパターンをテキストと比較していき、もし最後の ‘B’ の手前の ‘A’ (P[7]) とテキストの対応文字が一致し、最後の ‘B’ (P[8]) で不一致になったとします。

テキスト T: ... ABABCABA B ... (← この'B'で不一致) パターン P: ABABCABA B (← この'B'と比較)

この不一致が発生した時点で、テキストのこの位置には「ABABCABA」という文字列が出現していることが分かっています。ナイーブ法なら、パターンを丸ごと右に1文字ずらして、テキストの次の位置から「ABABCABAB」との比較を始めます。これは多くの無駄な比較を招く可能性があります。

しかし、KMPアルゴリズムはここで考えます。「今、パターンは P[0] から P[7] まで一致した。つまり、テキストには ‘ABABCABA’ という文字列がある。この ‘ABABCABA’ という文字列の中に、パターンの先頭部分と同じ文字列が含まれていないだろうか？」と。

パターン P = “ABABCABAB” の P[0..7] は “ABABCABA” です。
この “ABABCABA” の接尾辞（サフィックス）を見てみましょう。
“A”, “BA”, “ABA”, “CABA”, “BCABA”, “ABСABA”, “BABСABA”, “ABABCABA”

そして、パターン全体の接頭辞（プレフィックス）を見てみましょう。
“A”, “AB”, “ABA”, “ABAB”, “ABABC”, “ABabca”, “ABABCAB”, “ABABCABA”, “ABABCABAB”

“ABABCABA” の中で、最も長い「パターン全体の接頭辞」と一致する「真の接尾辞」（文字列自身を除く接尾辞）は何でしょうか？
比較すると、「ABA」が共通しています。

ABABCABA (P[0..7]) 接頭辞: A, AB, *ABA*, ABAB, ... 接尾辞: A, BA, *ABA*, CABA, ...

最も長い共通部分は “ABA” で、その長さは3です。
これは何を意味するでしょうか？パターンの P[0..7] がテキストと一致したということは、テキストのその部分の末尾3文字は “ABA” であり、これはパターンの先頭3文字 (P[0..2]) と同じ文字列である、ということです。

“`
テキスト T: … [ABABC]ABA B … (← ‘B’で不一致)
^^^^^^^^
P[0..7] と一致

パターンの先頭 3文字: ABA
テキストの該当部分の末尾 3文字: ABA
“`

つまり、テキストのその位置には「…ABA」という部分があり、これはパターンの先頭「ABA」と一致しているのです。

したがって、パターンを単に1文字ずらすのではなく、パターンの「接頭辞であると同時に接尾辞でもある部分」を利用して、パターンの比較位置をジャンプさせることができるのです。具体的には、不一致が起こった位置 j までのパターン P[0..j-1] において、最も長い「真の接頭辞」であり、かつ「真の接尾辞」である文字列の長さを k とします。不一致が発生した場合、パターンを j の位置から比較する代わりに、k の位置から比較を再開すれば良いのです。これにより、すでに一致が分かっている k 文字分の比較を省略し、パターンを j - k 文字分だけ右にシフトさせることができます。

この「不一致時にパターンの比較を再開すべき位置（または、どれだけシフトできるか）」を効率的に判断するための情報が、KMPアルゴリズムの中核をなす「失敗関数（Failure Function）」、あるいは「プレフィックス関数（Prefix Function）」または「π関数」と呼ばれるものです。

KMPアルゴリズムの鍵：失敗関数（π関数）

KMPアルゴリズムの効率性は、検索を開始する前にパターン自身を解析して計算される失敗関数（failure function）、あるいはプレフィックス関数（prefix function, π関数）と呼ばれる補助的な配列にあります。この関数（配列）は、パターンの中で不一致が起こった際に、パターンの比較をどの位置から再開すれば最も効率的かを教えてくれます。

π関数の定義は以下のようになります。
パターンの長さ $m$ の文字列 $P$ に対して、π関数（配列）π は長さ $m$ の配列です。
$\pi[j]$ の値 ($0 \leq j < m$) は、「パターン $P$ の $0$ 番目の文字から $j$ 番目の文字まで ($P[0..j]$) の部分文字列」において、「最も長い、空でない真の接頭辞であり、同時に真の接尾辞である文字列の長さ」 を示します。

「真の接頭辞」とは、文字列自身を含まない接頭辞のことです。例えば、文字列 “ABCD” の真の接頭辞は “A”, “AB”, “ABC” です。「真の接尾辞」も同様に、文字列自身を含まない接尾辞です。”ABCD” の真の接尾辞は “D”, “CD”, “BCD” です。

例えば、パターン P = “ABABCABAB” を例に、π関数を計算してみましょう。パターンの長 $m=9$ なので、π配列のサイズは 9 になります (π[0] から π[8])。

π[0]: パターンの最初の文字 P[0] (“A”)。この部分文字列 “A” の空でない真の接頭辞も真の接尾辞も存在しないため、π[0] = 0 です。
π[1]: パターンの P[0..1] (“AB”)。真の接頭辞は “A”、真の接尾辞は “B”。共通部分はありません。π[1] = 0 です。
π[2]: パターンの P[0..2] (“ABA”)。真の接頭辞は “A”, “AB”。真の接尾辞は “A”, “BA”。最も長い共通部分は “A” です。その長さは 1 です。π[2] = 1 です。
π[3]: パターンの P[0..3] (“ABAB”)。真の接頭辞は “A”, “AB”, “ABA”。真の接尾辞は “B”, “AB”, “BAB”。最も長い共通部分は “AB” です。その長さは 2 です。π[3] = 2 です。
π[4]: パターンの P[0..4] (“ABABC”)。真の接頭辞は “A”, “AB”, “ABA”, “ABAB”。真の接尾辞は “C”, “BC”, “ABC”, “BABC”。共通部分はありません。π[4] = 0 です。
π[5]: パターンの P[0..5] (“ABabca”) -> 正しくは P[5]は’A’ なので “ABABCA“です。
パターンの P[0..5] (“ABABCA”)。真の接頭辞は “A”, “AB”, “ABA”, “ABAB”, “ABABC”。真の接尾辞は “A”, “CA”, “BCA”, “ABCA”, “BABCA”。最も長い共通部分は “A” です。その長さは 1 です。π[5] = 1 です。
π[6]: パターンの P[0..6] (“ABABCAB”)。真の接頭辞は “A”, “AB”, …, “ABabca”。真の接尾辞は “B”, “AB”, …, “ABABCAB”。最も長い共通部分は “AB” です。その長さは 2 です。π[6] = 2 です。
π[7]: パターンの P[0..7] (“ABABCABA”)。真の接頭辞は “A”, “AB”, …, “ABABCAB”。真の接尾辞は “A”, “BA”, …, “ABABCABA”。最も長い共通部分は “ABA” です。その長さは 3 です。π[7] = 3 です。
π[8]: パターンの P[0..8] (“ABABCABAB”)。真の接頭辞は “A”, “AB”, …, “ABABCABA”。真の接尾辞は “B”, “AB”, …, “ABABCABAB”。最も長い共通部分は “ABAB” です。その長さは 4 です。π[8] = 4 です。

したがって、パターン “ABABCABAB” のπ関数は [0, 0, 1, 2, 0, 1, 2, 3, 4] となります。

このπ関数は、パターンの長さ $m$ に対して線形時間 $O(m)$ で効率的に計算できます。計算アルゴリズムは、動的計画法的なアプローチを取ります。π[0] は常に 0 です。そして、π[j] を計算するために、π[j-1] までの情報（より短い接頭辞/接尾辞の情報）を利用します。

π関数の計算アルゴリズム（例：「ABABCABAB」）:

π配列 (長さ m) を用意。π[0] = 0。
k を 0 で初期化します。k は、現在着目している接頭辞/接尾辞の一致している長さを示します。

j を 1 から $m-1$ までループします。
各ステップ j では、P[0..j] に対する π[j] を計算します。これは、P[j] を追加したことで、P[0..j-1] の最も長い接頭辞/接尾辞 (長さ π[j-1]) がどのように変化するかを考えます。

現在の一致している長さ k は、π[j-1] の値に対応するパターンの文字 P[k] と、現在の着目文字 P[j] を比較します。
P[j] と P[k] が一致する場合: P[0..j] における最も長い接頭辞/接尾辞の長さは、P[0..j-1] のそれ (k) より 1 増えます。つまり、π[j] = k + 1 となります。そして、次回の比較のために k を k + 1 に更新します。
P[j] と P[k] が一致しない場合: これまで一致していた k の長さでは、P[j] と P[k] がつながりません。この場合、より短い接頭辞/接尾辞の一致を探す必要があります。π関数の定義によれば、不一致が起きた P[k] の代わりに、π[k-1] の位置にある文字 (P[π[k-1]]) と P[j] を比較し直します。これは、一致している接頭辞 P[0..k-1] において、その中で最も長い接頭辞/接尾辞の長さ π[k-1] を次の候補とするということです。これを k が 0 になるまで (P[j] と P[0] を比較するまで) 繰り返します。
- k > 0 ならば、k を π[k-1] に更新し、再度 P[j] と P[k] を比較します (while ループになります)。
- k が 0 になった場合 (P[j] がパターンの最初の文字 P[0] とも一致しなかった場合)、P[0..j] には P[0] から始まる接頭辞と一致する空でない接尾辞は存在しないことになります。したがって、π[j] = 0 となります。そして、次回の比較のために k は 0 のままです。

このアルゴリズムの計算量が O(m) である理由は、各ステップ j (1から m-1) において、k は最大で 1 増加するか、または π[k-1] の値まで減少するからです。k は最大で m までしか増加しません。k が減少するステップ (k = π[k-1]) では、k の値が減少することは保証されており、その減少量の合計は k が増加した合計量を超えることはありません。したがって、k の合計増加量と合計減少量の和は $O(m)$ に収まり、各文字 P[j] は高々定数回しか比較されないため、π配列全体の計算量は線形時間 $O(m)$ となります。

このπ関数こそが、KMPアルゴリズムがナイーブ法と比べて高速に検索できる秘密兵器なのです。π関数によって、パターンの各位置で不一致が起こった際に、パターンをどれだけ効率的にシフトできるかが事前に分かります。

KMP検索アルゴリズムの詳細

π関数の計算が終われば、いよいよ実際の文字列検索を行います。KMPの検索アルゴリズムは、テキスト $T$（長さ $n$）、パターン $P$（長さ $m$）、そして事前に計算したπ関数（配列）を利用します。

検索は、テキストのインデックス i とパターンのインデックス j を使って行われます。i はテキストの現在の比較位置、$j$ はパターンの現在の比較位置を示します。最初は i = 0, j = 0 です。

アルゴリズムの基本的な流れは以下のようになります。テキストのインデックス i がテキストの長さ $n$ に達するまで繰り返します。

文字の比較: T[i] と P[j] を比較します。
一致する場合:
- T[i] と P[j] が一致したら、次の文字の比較に進みます。テキストとパターンの両方のインデックスを 1 増加させます (i++, j++)。
パターン全体が一致した場合:
- もし j がパターンの長さ m に達したら、テキストの i-m の位置でパターンが完全に一致したことを意味します。一致が見つかりました！
- 一致を見つけた後、さらにテキスト中にパターンが出現する可能性を探る場合、パターンの比較位置 j を、π関数を使って効率的にシフトさせます。完全に一致したパターン P[0..m-1] に基づくシフトなので、j = π[m-1] とします。テキストのインデックス i はそのままです（∵テキストの後戻りなし）。
不一致が発生した場合:
- T[i] と P[j] が一致しなかった場合、現在のパターンの位置 j で不一致が起きたことになります。
- もし j が 0 でない場合（パターンの途中で不一致が起きた場合）: ナイーブ法のようにテキストの開始位置を1つずらしてパターン全体を比較し直すのではなく、π関数を利用します。π[j-1] の値は、不一致が起きた P[j] の直前までのパターン P[0..j-1] の中で、最も長い「真の接頭辞」であり「真の接尾辞」である部分の長さです。このπ[j-1] の長さの接頭辞と、テキストの現在の位置 i の手前までに一致していた部分の接尾辞が一致していることがπ関数の定義から分かります。したがって、次に比較すべきパターンの位置は j の値ではなく、π[j-1] の値が示す位置 (P[π[j-1]]) となります。つまり、j を π[j-1] に更新します。テキストのインデックス i はそのままです。
- もし j が 0 の場合（パターンの最初の文字で不一致が起きた場合）: パターンの先頭 P[0] がテキストの T[i] と一致しなかったということなので、パターン全体を右に1文字ずらすしかありません。この場合、テキストのインデックス i を 1 増加させ (i++)、パターンのインデックス j は 0 のまま（パターンの最初）で比較を続けます。

テキストのインデックス i が $n$ に達したら、検索は終了です。

このアルゴリズムは、ナイーブ法と異なり、不一致が発生してもテキスト側のインデックス i を後戻りさせません。i は一致した時に増加するか、パターンの最初の文字で不一致だった時に増加するかのどちらかです。パターンのインデックス j は一致すれば増加しますが、不一致の場合はπ関数に従って減少します。しかし、j がπ関数によって減少するのは、それ以前に j が一致によって増加した分があるからです。

具体的な例で、KMP検索アルゴリズムの動作を追ってみましょう。
テキスト T = “ABABDABACDABABCABAB” (n=20)
パターン P = “ABABCABAB” (m=9)
π関数 = [0, 0, 1, 2, 0, 1, 2, 3, 4]

初期状態: 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]==’A’, P[2]==’A’. 一致. i=3, j=3.
i=3, j=3: T[3]==’B’, P[3]==’B’. 一致. i=4, j=4.
i=4, j=4: T[4]==’D’, P[4]==’C’. 不一致. j!=0 (j=4). j = π[j-1] = π[3] = 2. iは4のまま.
T: ABAB D ... P: ABABC ... ^不一致一致していた部分: T[0..3] == P[0..3] ("ABAB") P[0..3] = "ABAB" のπ[3]=2。これは P[0..1] ("AB") が P[2..3] ("AB") と一致することを示す。テキストの T[0..3] が "ABAB" と分かっている。 T[2..3] も "AB" である。パターンの P[0..1] も "AB" である。なので、パターンを P[0..1] が T[2..3] に合うようにシフトできる。
T: ABAB D ... P: ABABC ... ^ 次の比較開始位置 (j=2)
i=4, j=2: T[4]==’D’, P[2]==’A’. 不一致. j!=0 (j=2). j = π[j-1] = π[1] = 0. iは4のまま.
T: ABABD ... P: ABANC ... (← ABANCではなくABABC) ^不一致 (P[2] vs T[4]) 一致していた部分: P[0..1] と T[2..3] が比較されていた状態。今回は不一致でj=2に来たが、 T[0..3] と P[0..3] が一致した後の不一致からジャンプしてきた状態。現在の比較位置は T[4] と P[2]。T[4] ('D') と P[2] ('A') が不一致。不一致が起きたのはパターンの j=2 の位置。直前まで一致していたのは P[0..1] と T[i-2 .. i-1] (?) いや、この時点での i=4, j=2 は、テキストの T[i] とパターンの P[j] を比較している状態。 T[4] と P[2] の比較で不一致。不一致が起きたのはパターン P の j=2 の位置。直前まで一致していたのは P[0..1] と T[2..3] か？いいえ、直前の状態は i=4, j=4 で不一致、j = π[3] = 2 となった直後です。不一致が発生したパターン位置は P[j] = P[4] でした。その時の `j` は 4 です。不一致が発生した一つ前のパターン位置は P[j-1] = P[3] です。不一致が発生した `j` の位置から、π[j-1] = π[3] = 2 へジャンプしました。これは、パターン P[0..j-1] == T[i-j..i-1] が一致しており、P[j] != T[i] であった場合に、次に T[i] と比較すべきパターン文字は P[π[j-1]] である、という意味です。つまり、テキストの i の位置はそのままで、パターンの比較位置を j から π[j-1] に戻すのです。
現在 i=4, j=2。T[4] vs P[2]。不一致。j!=0 (j=2)。j = π[j-1] = π[1] = 0。iは4のまま。
T: ABABD ... P: ABANC ... (← ABABC) ^不一致 (P[2] vs T[4]) 不一致が起きたのはパターンPのj=2の位置。π[2-1] = π[1] = 0。次に比較すべきパターン文字は P[π[1]] = P[0]。
T: ABABD …
P: ABABC …
^ 次の比較開始位置 (j=0)
“`
i=4, j=0: T[4]==’D’, P[0]==’A’. 不一致. j==0. i=5, j=0. (テキストを1つ進める)
T: ABABD ... P: ABABC ... ^ テキスト次の比較開始位置 (i=5) ^ パターン比較開始位置 (j=0)
i=5, j=0: T[5]==’A’, P[0]==’A’. 一致. i=6, j=1.
i=6, j=1: T[6]==’B’, P[1]==’B’. 一致. i=7, j=2.
i=7, j=2: T[7]==’A’, P[2]==’A’. 一致. i=8, j=3.
i=8, j=3: T[8]==’C’, P[3]==’B’. 不一致. j!=0 (j=3). j = π[j-1] = π[2] = 1. iは8のまま.
T: ABABDABAC D ... P: ABABCABAB ^^^^不一致 (P[3] vs T[8]) 一致していた部分: P[0..2] と T[5..7] ("ABA") 不一致が起きた j=3 の直前は j-1=2。π[2]=1。次に比較すべきパターン文字は P[π[2]] = P[1]。テキストの T[8] はそのまま。パターンは j=3 から j=1 に戻る。
T: ABABDABAC D ... P: ABABCABAB ^ 次の比較開始位置 (j=1)
i=8, j=1: T[8]==’C’, P[1]==’B’. 不一致. j!=0 (j=1). j = π[j-1] = π[0] = 0. iは8のまま.
T: ABABDABAC D ... P: ABABCABAB ^不一致 (P[1] vs T[8]) 不一致が起きた j=1 の直前は j-1=0。π[0]=0。次に比較すべきパターン文字は P[π[0]] = P[0]。テキストの T[8] はそのまま。パターンは j=1 から j=0 に戻る。
T: ABABDABAC D ... P: ABABCABAB ^ 次の比較開始位置 (j=0)
i=8, j=0: T[8]==’C’, P[0]==’A’. 不一致. j==0. i=9, j=0. (テキストを1つ進める)
T: ABABDABAC D ... P: ABABCABAB ^ テキスト次の比較開始位置 (i=9) ^ パターン比較開始位置 (j=0)
i=9, j=0: T[9]==’D’, P[0]==’A’. 不一致. j==0. i=10, j=0.
i=10, j=0: T[10]==’A’, P[0]==’A’. 一致. i=11, j=1.
i=11, j=1: T[11]==’B’, P[1]==’B’. 一致. i=12, j=2.
i=12, j=2: T[12]==’A’, P[2]==’A’. 一致. i=13, j=3.
i=13, j=3: T[13]==’B’, P[3]==’B’. 一致. i=14, j=4.
i=14, j=4: T[14]==’C’, P[4]==’C’. 一致. i=15, j=5.
i=15, j=5: T[15]==’A’, P[5]==’A’. 一致. i=16, j=6.
i=16, j=6: T[16]==’B’, P[6]==’B’. 一致. i=17, j=7.
i=17, j=7: T[17]==’A’, P[7]==’A’. 一致. i=18, j=8.
i=18, j=8: T[18]==’B’, P[8]==’B’. 一致. i=19, j=9.
i=19, j=9: j==m (9). パターンがテキストの i-m = 19-9 = 10 の位置で見つかりました！
T: ABABDABACD ABABCABAB ^^^^^^^^^ <- マッチ！ (T[10..18]) P: ABABCABAB ^^^^^^^^^
次の出現を探すために、j = π[m-1] = π[8] = 4 に戻ります。iは19のまま。
T: ABABDABACD ABABCABAB ^^^^^^^^^ <- マッチした部分 P: ABABCABAB ^^^^ <- j=4から比較再開 π[8]=4は、パターン P[0..8] = "ABABCABAB" の中で、最も長い「真の接頭辞」であり「真の接尾辞」である部分の長さが4であること、その部分は P[0..3] = "ABAB" であることを示します。テキストの T[10..18] が "ABABCABAB" と一致したということは、T[15..18] は "ABAB" です。パターンの P[0..3] は "ABAB" です。したがって、パターンを P[0..3] が T[15..18] と一致するようにシフトすることができます。これは、パターンを i-m の位置ではなく、(i-m) + (m - π[m-1]) の位置にシフトすることと同じです。新しい比較は T[i] (T[19]?) と P[π[m-1]] (P[4]) から始まります。
i=19, j=4: (i < n = 20 は真) T[19]==’B’, P[4]==’C’. 不一致. j!=0 (j=4). j = π[j-1] = π[3] = 2. iは19のまま.
T: ...B (T[19]) P: ...C (P[4]) ^不一致不一致が起きた j=4 の直前 j-1=3。π[3]=2。次に比較すべきパターン文字は P[π[3]] = P[2]。
i=19, j=2: T[19]==’B’, P[2]==’A’. 不一致. j!=0 (j=2). j = π[j-1] = π[1] = 0. iは19のまま.
T: ...B (T[19]) P: ...A (P[2]) ^不一致不一致が起きた j=2 の直前 j-1=1。π[1]=0。次に比較すべきパターン文字は P[π[1]] = P[0]。
i=19, j=0: T[19]==’B’, P[0]==’A’. 不一致. j==0. i=20, j=0.
T: ...B (T[19]) P: ...A (P[0]) ^不一致パターンの先頭で不一致。テキストを1つ進める。i=20。
i=20, j=0: i < n (20 < 20) は偽。ループ終了。

検索が終了し、パターンがテキストのインデックス 10 の位置に一度出現したことが分かりました。

このトレースを見ると分かるように、KMPアルゴリズムはナイーブ法と異なり、不一致が発生してもテキストポインタ i を後戻りさせません。パターンのポインタ j だけがπ関数に従って効率的にジャンプすることで、無駄な比較をスキップしています。

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

KMPアルゴリズムの計算時間は、以下の2つのフェーズに分けられます。

π関数の前計算: パターンの長さ $m$ に対して $O(m)$ の時間が必要です。前述したπ関数の計算アルゴリズムは、各ステップ j で k が高々1増加するか、または減少するという性質により線形時間となります。
検索: テキストの長さ $n$ に対して $O(n)$ の時間が必要です。検索プロセスでは、テキストのインデックス i は常に増加するか（一致した場合、またはパターンの先頭で不一致だった場合）、またはそのまま維持されます（パターンの途中で不一致の場合、j だけが減少）。i が後戻りすることはありません。また、パターンのインデックス j は一致すれば増加し、不一致で j > 0 の場合はπ関数によって減少します。j が減少する回数は、それまでに j が増加した回数を超えることはありません。テキストの各文字 T[i] は、高々定数回の比較 (P[j] との比較、そして不一致時の P[π[...]] との比較など) しか行われません。したがって、検索フェーズ全体の計算量は線形時間 $O(n)$ となります。

KMPアルゴリズム全体の計算量は、π関数の前計算と検索時間の合計であり、$O(m) + O(n) = O(n+m)$ となります。

これは、ナイーブ法の最悪ケース $O(nm)$ と比較して格段に高速です。KMPアルゴリズムは、テキストやパターンの内容に関わらず、常に線形時間で検索を完了できるという強力な保証を持っています。

KMPアルゴリズムの利点と他のアルゴリズムとの比較

KMPアルゴリズムの主な利点は以下の通りです。

線形時間計算量: テキストとパターンの長さに比例した時間で検索を完了できます ($O(n+m)$)。これは理論的な最速に非常に近いパフォーマンスです。
最悪ケース性能: どのような入力に対してもパフォーマンスが劣化せず、常に線形時間で動作します。ナイーブ法のような特定の入力で極端に遅くなることがありません。
テキストポインタの後戻りなし: テキストのインデックス i が常に単調増加（または維持）するため、テキスト全体を一度だけスキャンすれば良いことになります。これは、ストリーム処理など、テキストを一度に全てメモリにロードできないような状況で特に有利です。

一方で、KMPアルゴリズムには以下の考慮事項もあります。

π関数の前計算が必要: 検索を開始する前に、パターンの長さ分のπ配列を計算し、メモリに保持する必要があります。これはパターンの長さに応じた追加の処理時間とメモリを必要とします（ただし線形時間・空間なので大きな問題になりにくい）。
平均的な性能: 一部の他のアルゴリズム（例: Boyer-Moore法）は、特定の種類のテキストやパターンにおいては、平均的な検索速度でKMPよりも高速になることがあります。これは、Boyer-Moore法が不一致時にKMPよりも大きなジャンプをすることが期待できるためです。
アルゴリズムの複雑さ: ナイーブ法と比べると、π関数の概念やその計算、検索時のジャンプロジックの理解がやや複雑です。

他の代表的な文字列検索アルゴリズムと比較すると、KMPアルゴリズムは以下のような位置づけになります。

ナイーブ法 (Simple/Brute Force): 実装が最も容易。計算量は $O(nm)$（最悪）。非常に非効率になる場合がある。
Rabin-Karp法: ローリングハッシュを利用。平均計算量は $O(n+m)$ ですが、ハッシュの衝突によっては最悪ケースで $O(nm)$ になる可能性があります。複数パターンの検索に強いという利点があります。
Boyer-Moore法: パターンの右端から比較を開始する。不一致時に、パターンの文字やそれまでに一致したテキストの文字に基づいて、KMPよりも大きなジャンプをすることが期待できます。平均計算量は $O(n/m)$ に近いことが多く、多くの実用的なケースで最も高速なアルゴリズムの一つとされています。ただし、最悪ケースは $O(nm)$ になり得ますが、実用的な派生アルゴリズムで改善されています。π関数に類似した「Suffix Rule」と、不一致文字に基づく「Bad Character Rule」という2つのヒューリスティックを組み合わせます。
KMP法: 線形時間 $O(n+m)$ を常に保証します。テキストの後戻りがありません。特にパターンの繰り返しが多い場合にKMPの効率性が光ります。

このように、KMPアルゴリズムは「常に線形時間で、テキストを一度のスキャンで検索できる」という強力な特性を持っており、特定の応用分野で非常に有効です。

KMPアルゴリズムの応用例

KMPアルゴリズムの効率性と特性は、様々な分野で活用されています。

テキストエディタやワープロソフト: ドキュメント内の高速な検索・置換機能の実装に利用されることがあります。特に大きなファイルや長い行を含む場合に、その線形時間性能が役立ちます。
プログラミング言語処理系 (コンパイラ、インタプリタなど): ソースコードの字句解析（Lexical Analysis）の段階で、予約語や識別子などのパターンを効率的に検出するために使用されることがあります。
ネットワークセキュリティ: 侵入検知システム（IDS）などで、ネットワークパケットのペイロードの中から既知の攻撃パターン（シグネチャ）を高速に検索するために使われることがあります。
バイオインフォマティクス: DNAやタンパク質の長い塩基配列/アミノ酸配列の中から、特定のパターンやモチーフを検索する際に利用されることがあります。配列データは非常に長くなるため、高速な検索アルゴリズムが不可欠です。
データ圧縮: 一部の圧縮アルゴリズムで、繰り返し出現するパターンを検出するために、文字列検索の技術が応用されます。

これらの応用分野は、大量のデータの中から特定のパターンを効率的に見つけ出す必要があるという共通の特徴を持っています。KMPアルゴリズムの線形時間性能は、このような要求に応える強力な基盤となります。

まとめ

本記事では、高速な文字列検索アルゴリズムであるKMP法について、その基本的な考え方、核となるπ関数の詳細、そして実際の検索アルゴリズムの動作を、素朴なナイーブ法との比較を交えながら詳しく解説しました。

KMPアルゴリズムの鍵は、パターンが持つ「自身の接頭辞が接尾辞として出現する」という構造を解析し、不一致が発生した際にテキストポインタを後戻りさせることなく、パターンの比較位置を効率的にジャンプさせるπ関数にあります。このπ関数を前計算するフェーズが $O(m)$、そしてπ関数を利用して検索を行うフェーズが $O(n)$ の計算量となり、合計で常に線形時間 $O(n+m)$ で検索を完了できることがKMPアルゴリズムの最大の特長です。

ナイーブ法のような単純な方法が特定の最悪ケースでパフォーマンスが著しく劣化するのに対し、KMP法は入力データの内容に依存せず、常に安定した高速な性能を発揮します。テキストを一度だけスキャンすれば良いという特性は、メモリ効率の面でも利点となり得ます。

Boyer-Moore法など、平均的にはより高速なアルゴリズムも存在しますが、KMPアルゴリズムが提供する「最悪ケースでも線形時間」という保証と、テキストの後戻りがないという特性は、特定の用途においては依然として非常に価値が高く、文字列検索アルゴリズムの歴史において重要な位置を占めています。

KMPアルゴリズムの理解は、より高度な文字列処理やパターンマッチングアルゴリズムを学ぶ上での強固な基礎となります。その洗練されたアイデアは、コンピュータサイエンスにおける効率的なアルゴリズム設計の好例と言えるでしょう。この記事が、皆さんがKMPアルゴリズムの基本とその魅力について理解を深める一助となれば幸いです。高速な文字列検索の世界は奥深く、KMPはその重要な一歩となるでしょう。