---

文字列検索を効率化！KMPアルゴリズムの基礎とメリット

はじめに：文字列検索の重要性とナイーブ法の限界

コンピュータを使って情報を扱う上で、「文字列検索」は非常に基本的な操作です。例えば、テキストエディタで特定の単語を探したり、Webブラウザでキーワードを入力して情報を検索したり、プログラミングコードの中から関数名を探したり。これらはすべて文字列検索の応用例です。さらに、生物学におけるDNA配列の解析、ネットワークセキュリティにおけるパケットのパターンマッチング、データ圧縮など、文字列検索技術は様々な分野でその力を発揮しています。

最もシンプルで直感的な文字列検索方法として、「ナイーブ法（単純な方法）」があります。これは、テキストの中からパターン（検索したい文字列）を見つけ出す際に、テキストの先頭から順にパターンとの一致を試みていく方法です。

例えば、テキストT = "ABABABCA"の中から、パターンP = "ABCA"を探す場合を考えてみましょう。

1. テキストの最初の文字Aとパターンの最初の文字Aを比較します。一致。
2. テキストの2番目の文字Bとパターンの2番目の文字Bを比較します。一致。
3. テキストの3番目の文字Aとパターンの3番目の文字Cを比較します。不一致。

ここでナイーブ法は、テキストの比較開始位置を1つずらし、パターンの比較を最初からやり直します。

1. テキストの2番目の文字Bとパターンの最初の文字Aを比較します。不一致。
2. テキストの比較開始位置を1つずらし、テキストの3番目の文字Aとパターンの最初の文字Aを比較します。一致。
3. テキストの4番目の文字Bとパターンの2番目の文字Bを比較します。一致。
4. テキストの5番目の文字Aとパターンの3番目の文字Cを比較します。不一致。

再び、テキストの比較開始位置を1つずらし、パターンの比較を最初からやり直します。

1. テキストの4番目の文字Bとパターンの最初の文字Aを比較します。不一致。
2. テキストの比較開始位置を1つずらし、テキストの5番目の文字Aとパターンの最初の文字Aを比較します。一致。
3. テキストの6番目の文字Bとパターンの2番目の文字Bを比較します。一致。
4. テキストの7番目の文字Cとパターンの3番目の文字Cを比較します。一致。
5. テキストの8番目の文字Aとパターンの4番目の文字Aを比較します。一致。

パターンが見つかりました。テキストの5番目の位置からパターンが開始しています。

このように、ナイーブ法は非常に分かりやすいアルゴリズムです。しかし、この例からも分かるように、不一致が発生するたびにテキストの比較開始位置をわずかに（通常は1文字）ずらし、パターンの比較を先頭からやり直すというプロセスは、非常に無駄が多い場合があります。

特に、テキストとパターンが部分的に長く一致した後に不一致が発生する場合、ナイーブ法はテキストの比較位置を大きく巻き戻す必要が生じます。例えば、テキストT = "AAAAAAAAB"の中からパターンP = "AAAAB"を探す場合を考えてみましょう。

テキスト: AAAAAAAAB
パターン: AAAAB

1. テキストの先頭から4文字がパターンと一致 (AAAA) しますが、5文字目で不一致 (A vs B)。
2. ナイーブ法はテキストの比較位置を2番目のAに戻し、パターンを先頭から比較します。
3. 再びテキストの2番目から4文字がパターンと一致 (AAAA) しますが、5文字目で不一致。
4. テキストの比較位置を3番目のAに戻し、パターンを先頭から比較します。

…この処理が繰り返されます。テキスト長をN、パターン長をMとすると、最悪の場合、ナイーブ法の計算量は O(N * M) となります。これは、例えばテキスト長が100万、パターン長が1000の場合、最大で10億回の文字比較が必要になる可能性があることを意味します。このような非効率性は、大規模なデータやリアルタイム性が求められるアプリケーションにおいては大きな問題となります。

そこで登場するのが、より効率的な文字列検索アルゴリズムです。その中でも代表的かつ基礎となるのが、この記事で解説する「KMPアルゴリズム」です。KMPアルゴリズムは、ナイーブ法の非効率性の原因である「不一致発生時の無駄な再探索」を劇的に削減することで、高速な文字列検索を実現します。

この記事では、KMPアルゴリズムがどのようにしてナイーブ法の課題を克服するのか、その基本的な仕組み、核となる「プレフィックス関数（失敗関数）」の詳細、実際の検索処理、そしてそのメリットと応用例について、分かりやすく詳細に解説していきます。KMPアルゴリズムの理解は、より高度な文字列処理技術やアルゴリズムを学ぶ上での重要な基礎となるでしょう。

KMPアルゴリズムの概要：既知情報を活用する賢い方法

KMPアルゴリズムは、Knuth、Morris、Prattという3人の計算機科学者によって考案された線形時間文字列検索アルゴリズムです。ナイーブ法が不一致時にテキストの比較開始位置を（ほとんどの場合）1文字ずつ進めるのに対し、KMPアルゴリズムは、パターン自身が持つ構造（自己相関）を利用して、不一致が発生した際に次に比較すべき位置を効率的に決定します。

KMPアルゴリズムの主要なアイデアは以下の2点に集約されます。

1. 不一致が発生した際、テキスト中の比較位置を戻さない。 テキストの読み込みは常に前方へ進むか、あるいは現在の位置でパターンのシフトを行うだけです。
2. 不一致が発生した際、それまで一致していたパターンの部分文字列の中に、次の比較開始位置に関する有用な情報が含まれている。 この「有用な情報」を事前に計算しておくことで、不一致時のパターンのシフト量を決定します。

この2つ目のアイデアを実現するのが、「プレフィックス関数（または失敗関数、next配列などとも呼ばれます）」と呼ばれるものです。プレフィックス関数は、検索処理を開始する前にパターンに対して一度だけ計算されます。この関数は、パターン内の各位置において、「そこまでの部分文字列において、最も長い真の接頭辞と接尾辞が一致する長さ」を示します。一見難しそうですが、具体例を見ると理解できます。

例えば、パターン P = "ABABCA" を考えます。

• P[0] (A): 接頭辞/接尾辞なし → 長さ 0
• P[0...1] (AB): 真の接頭辞 (A), 真の接尾辞 (B) → 一致なし → 長さ 0
• P[0...2] (ABA): 真の接頭辞 (A, AB), 真の接尾辞 (A, BA) → 最も長い一致は A → 長さ 1
• P[0...3] (ABAB): 真の接頭辞 (A, AB, ABA), 真の接尾辞 (B, AB, BAB) → 最も長い一致は AB → 長さ 2
• P[0...4] (ABABC): 真の接頭辞 (A, AB, ABA, ABAB), 真の接尾辞 (C, BC, ABC, BABC) → 一致なし → 長さ 0
• P[0...5] (ABABCA): 真の接頭辞 (A, AB, ABA, ABAB, ABABC), 真の接尾辞 (A, CA, BCA, ABCA, BABCA) → 最も長い一致は A → 長さ 1

したがって、パターンP = "ABABCA"に対するプレフィックス関数（π配列）は、インデックス0から始まる各位置に対応して [0, 0, 1, 2, 0, 1] となります。

このπ配列がどのように役立つのでしょうか？
検索中に、テキストのi番目の文字とパターンのj番目の文字を比較していて、T[i] != P[j]という不一致が発生したとします。このとき、パターンPのインデックス0からj-1までの部分 (P[0...j-1]) は、テキストのi-j番目の位置からi-1番目の位置までと一致しています。

ナイーブ法では、テキストの比較開始位置をi-j+1に戻し、パターンの比較位置を0に戻していました。しかしKMPでは、P[0...j-1]という一致していた部分の情報を活用します。具体的には、P[0...j-1]の最も長い真の接頭辞でありかつ接尾辞である部分の長さがπ[j-1]です。これはつまり、パターンPの先頭π[j-1]文字が、テキストのi-j + (j - π[j-1]) = i - π[j-1]番目の位置からi-1番目の位置までと一致しているということです。

不一致が発生したのがパターンのj番目の文字 (P[j]) なので、次に比較すべきはテキストの現在の位置iと、パターンのπ[j-1]番目の文字 (P[π[j-1]]) です。これにより、パターンをj - π[j-1]だけスライドさせたことになります。パターンポインタjをπ[j-1]に移動させ、テキストポインタiはそのままにして比較を続行すれば、無駄な比較を省くことができるのです。もしjが0（パターンの先頭文字で不一致）ならば、パターンを1文字だけスライドさせ、テキストポインタiを1つ進めて比較を続行します。

このプレフィックス関数を事前に計算するステップがO(M)時間、そしてプレフィックス関数を使って検索を行うステップがO(N)時間で完了するため、KMPアルゴリズム全体の計算量は O(N + M) となります。これは、ナイーブ法の最悪計算量 O(N * M) と比べて大幅に優れており、特に長いテキストやパターンに対してその効果を発揮します。

KMPアルゴリズムは、このプレフィックス関数（π配列）の計算と、それを利用した効率的な検索処理という二つのフェーズで構成されます。次に、この核となるプレフィックス関数について、さらに深く掘り下げて見ていきましょう。

KMPアルゴリズムの中核：プレフィックス関数（失敗関数、next配列）の詳細

KMPアルゴリズムの効率性は、パターンの構造を解析して作られる「プレフィックス関数」にかかっています。この関数は通常、π（パイ）という記号で表される配列として実装されるため、π配列と呼ばれることが多いです。別の呼び方として、失敗関数（Failure Function）やnext配列と呼ばれることもあります。

プレフィックス関数 π[j] の定義

パターン文字列を P とし、その長さを M とします。プレフィックス関数 π は長さ M の配列で、π[j] (0 <= j < M) は以下のように定義されます。

π[j]：パターン P の接頭辞 P[0...j] において、最も長い真の接頭辞であり、かつ、その同じ文字列が接尾辞にもなっているような部分文字列の長さ。

ここで、「真の接頭辞」とは、文字列自身を含まない接頭辞のことです（例: ABC の真の接頭辞は A, AB）。同様に、「真の接尾辞」も文字列自身を含まない接尾辞のことです（例: ABC の真の接尾辞は C, BC）。

例として、パターン P = "ABACABA" のπ配列を計算してみましょう。パターン長 M = 7 です。

• j = 0: P[0] = "A". 真の接頭辞/接尾辞はありません。長さは 0 です。 π[0] = 0。
• j = 1: P[0...1] = "AB". 真の接頭辞 (A), 真の接尾辞 (B). 一致する真の接頭辞/接尾辞はありません。長さは 0 です。 π[1] = 0。
• j = 2: P[0...2] = "ABA". 真の接頭辞 (A, AB), 真の接尾辞 (A, BA). 一致するのは "A" です。最も長い一致部分の長さは 1 です。 π[2] = 1。
  • ABA
  • ^ (接頭辞 ‘A’)
  • ^ (接尾辞 ‘A’)
• j = 3: P[0...3] = "ABAC". 真の接頭辞 (A, AB, ABA), 真の接尾辞 (C, AC, BAC). 一致する真の接頭辞/接尾辞はありません。長さは 0 です。 π[3] = 0。
• j = 4: P[0...4] = "ABACA". 真の接頭辞 (A, AB, ABA, ABAC), 真の接尾辞 (A, CA, ACA, BACA). 一致するのは "A" です。最も長い一致部分の長さは 1 です。 π[4] = 1。
  • ABACA
  • ^ (接頭辞 ‘A’)
  • ^ (接尾辞 ‘A’)
• j = 5: P[0...5] = "ABACAB". 真の接頭辞 (A, AB, ABA, ABAC, ABACA), 真の接尾辞 (B, AB, CAB, ACAB, BACAB). 一致するのは "AB" です。最も長い一致部分の長さは 2 です。 π[5] = 2。
  • ABACAB
  • ^^ (接頭辞 ‘AB’)
  • ^^^^ (接尾辞 ‘AB’)
• j = 6: P[0...6] = "ABACABA". 真の接頭辞 (A, AB, ABA, ABAC, ABACA, ABACAB), 真の接尾辞 (A, BA, ABA, CABA, ACABA, BACABA). 一致するのは "A", "ABA" です。最も長い一致部分は "ABA" です。長さは 3 です。 π[6] = 3。
  • ABACABA
  • ^^^ (接頭辞 ‘ABA’)
  • ^^^ (接尾辞 ‘ABA’)

したがって、パターン P = "ABACABA" のπ配列は [0, 0, 1, 0, 1, 2, 3] となります。

このπ配列の値 π[j] は、検索処理において、パターン P[0...j] の位置 j で不一致が発生した場合に、次にパターンのどの位置（インデックス）と比較を開始すればよいかを示しています。具体的には、不一致が発生したパターン上の位置が j であった場合、次に比較すべきパターンの位置は π[j-1] になります（0-based indexの場合）。例えば P = "ABACABA" で j=6 の位置 (P[6] = 'A') で不一致が起きたとします。その直前まで P[0...5] は一致していたことになります。π[5] = 2 なので、次に比較すべきパターン上の位置はインデックス 2 (P[2] = 'A') となります。これは、P[0...5] の接尾辞 P[4...5] ("AB") が、接頭辞 P[0...1] ("AB") と一致していることから、パターンの先頭2文字は既に一致しているとみなせるからです。

π配列の計算アルゴリズム

π配列は、パターンの各位置 j (1からM-1まで) について、π[j] の値を計算していくことで求められます。この計算は効率的に、線形時間 O(M) で行うことができます。π配列の計算自体も、KMPアルゴリズムの考え方（これまでの情報を使って次に進むべき位置を判断する）に基づいています。

計算は、パターン P のインデックス j を 1 から M-1 まで進めながら行います。同時に、現在計算中の j において、最も長い真の接頭辞/接尾辞一致の長さ k を追跡します。k は次に比較すべきパターンの接頭辞の長さ（つまり、π配列のインデックス）を表します。

初期状態：
* π[0] = 0 （定義により）
* 現在の接頭辞/接尾辞一致の長さ k = 0

j を 1 から M-1 までループさせながら：
1. パターン P の現在の文字 P[j] と、現在の接頭辞の次の文字 P[k] を比較します。
2. P[j] と P[k] が一致する場合：
* 一致する接頭辞/接尾辞の長さが1増えます。k をインクリメントします。
* 現在の位置 j におけるπ値は k になります。π[j] = k。
* 次に進みます (j をインクリメントして次のループへ)。
3. P[j] と P[k] が一致しない場合：
* これは、長さ k の接頭辞が接尾辞として一致しなかったということです。より短い接頭辞での一致を探す必要があります。
* π配列の定義から、長さ k の接頭辞 P[0...k-1] の中で最も長い真の接頭辞/接尾辞一致の長さは π[k-1] です。つまり、次に試すべき接頭辞の長さは π[k-1] になります。
* そこで、k を π[k-1] に更新します。これは、パターンの接頭辞部分を「巻き戻す」操作に相当します。
* もし k が 0 になった（これ以上短い接頭辞でも一致するものがない）にも関わらずまだ P[j] と P[k] (P[0]) が一致しない場合、位置 j では接頭辞/接尾辞の一致がないことになります。このとき、π[j] = 0 となり、次のループへ進みます。もし k が 0 になって P[j] と P[k] (P[0]) が一致した場合は、k を 1 にして π[j] = 1 となり、次のループへ進みます。

このプロセスを擬似コードで表すと以下のようになります。

Function compute_prefix_function(P, M):
π = array of size M
π[0] = 0
k = 0 // k is the length of the previous longest prefix suffix
for j from 1 to M-1:
while k > 0 and P[j] != P[k]:
k = π[k-1] // Mismatch, move to the next shorter prefix suffix
if P[j] == P[k]:
k = k + 1 // Match, extend the prefix suffix length
π[j] = k
return π

例：P = "ABACABA", M=7

• π = [?, ?, ?, ?, ?, ?, ?]
• π[0] = 0, k = 0

j	P[j]	k (before comparison)	P[k]	P[j] == P[k] ?	while condition (k > 0 and P[j] != P[k])	New k	π[j]	π array state
1	B	0	A	No	False (k=0)	0	0	[0, 0, ?, ?, ?, ?, ?]
2	A	0	A	Yes	False	1	1	[0, 0, 1, ?, ?, ?, ?]
3	C	1	B	No	True (k=1>0, ‘C’!=’B’)	π[0]=0	0	0
4	A	0	A	Yes	False	1	1	[0, 0, 1, 0, 1, ?, ?]
5	B	1	B	Yes	False	2	2	[0, 0, 1, 0, 1, 2, ?]
6	A	2	A	Yes	False	3	3	[0, 0, 1, 0, 1, 2, 3]

結果：π = [0, 0, 1, 0, 1, 2, 3]。これは手動で計算した結果と一致します。

別の例：P = "AAAA", M=4

• π = [?, ?, ?, ?]
• π[0] = 0, k = 0

j	P[j]	k (before comp)	P[k]	P[j] == P[k] ?	while condition	New k	π[j]	π array state
1	A	0	A	Yes	False	1	1	[0, 1, ?, ?]
2	A	1	A	Yes	False	2	2	[0, 1, 2, ?]
3	A	2	A	Yes	False	3	3	[0, 1, 2, 3]

結果：π = [0, 1, 2, 3]。

また別の例：P = "ABCDEFG", M=7

• π = [?, ?, ?, ?, ?, ?, ?]
• π[0] = 0, k = 0

j	P[j]	k (before comp)	P[k]	P[j] == P[k] ?	while condition	New k	π[j]	π array state
1	B	0	A	No	False	0	0	[0, 0, ?, ?, ?, ?, ?]
2	C	0	A	No	False	0	0	[0, 0, 0, ?, ?, ?, ?]
3	D	0	A	No	False	0	0	[0, 0, 0, 0, ?, ?, ?]
…	…	…	…	No	False	0	0	…
6	G	0	A	No	False	0	0	[0, 0, 0, 0, 0, 0, 0]

結果：π = [0, 0, 0, 0, 0, 0, 0]。

このπ配列計算アルゴリズムは、各文字 P[j] について、内側の while ループは k の値を減少させる方向にしか進みません。k は π[k-1] に設定されるため、k は常に非負の値です。外側の for ループで j が1つ進むごとに、k は最大で1増加します (k+1になる場合)。内側の while ループでは k が減少し、0に達するまで繰り返しが行われます。k の値は全体で最大 M まで増加し、最大 M まで減少します。したがって、k の総増加量と総減少量は O(M) に抑えられます。各文字の比較は定数時間で行われるため、π配列計算全体の計算量は O(M) となります。これは非常に効率的です。

π配列の計算は、KMPアルゴリズムの「前処理」フェーズとして、検索を行う前に一度だけ実行されます。

KMPアルゴリズムの検索処理

π配列が計算できたら、いよいよテキストTの中からパターンPを検索する本処理に移ります。このフェーズでは、テキストの先頭から順に、パターンとの一致を試みます。不一致が発生した際には、事前に計算しておいたπ配列を使って、パターンの比較開始位置を適切にシフトさせます。

検索処理には、以下の2つのポインタを使用します。
* i: テキストTの現在の比較位置（インデックス）。0からスタートし、テキストの長さN-1まで進みます。
* j: パターンPの現在の比較位置（インデックス）。0からスタートし、パターンの長さM-1まで進みます。jは、現在テキストのi番目の文字と比較しているパターンの文字のインデックスであると同時に、テキストのiの位置でパターンPのj文字目までが一致していることを意味します。

検索処理のアルゴリズムは以下のようになります。

初期状態：
* i = 0 （テキストの開始位置）
* j = 0 （パターンの開始位置）
* 事前に計算したπ配列 π

ループ：テキストの最後まで（i < N）繰り返します。

1. 現在の文字が一致する場合 (T[i] == P[j])：

   • テキストのi番目の文字とパターンのj番目の文字が一致しました。
   • 両方のポインタを次に進めます。iをインクリメント、jをインクリメント。
   • もし j がパターン長 M に達した場合：
     • パターンがテキスト中に見つかったことになります（テキストのi-Mの位置から）。
     • 発見した位置を記録したり、何らかの処理を行います。
     • 検索を続ける場合、パターンをさらにシフトして次の出現を探します。このとき、パターンを全て一致させたので、次に比較すべきパターンの位置は π[M-1] になります。つまり、j を π[M-1] に更新します。テキストのポインタiはそのままです（あるいは、発見した位置の次の文字から再開するために、iをさらに進める実装もあり得ますが、KMPの標準的なシフトはj = π[M-1] です）。

2. 現在の文字が一致しない場合 (T[i] != P[j])：

   • テキストのi番目の文字とパターンのj番目の文字が一致しませんでした。
   • これは、パターンPのP[0...j]をテキストのT[i-j...i]と比較していて、T[i]とP[j]で失敗したということです。
   • ここでπ配列の出番です。パターンのポインタjを移動させますが、テキストのポインタiはそのままです。
   • もし j > 0 なら：
     • 不一致が発生したのがパターンの先頭文字 (j=0) ではない場合、これまでP[0...j-1]は一致していました。π配列の値 π[j-1] は、この一致していた部分P[0...j-1]の最も長い真の接頭辞/接尾辞一致の長さを示します。
     • この長さ π[j-1] を、次に比較を開始すべきパターンの位置とします。つまり、j を π[j-1] に更新します。テキストのi番目の文字は、次にP[π[j-1]]番目の文字と比較されることになります。テキストのポインタiは移動しません。
   • もし j == 0 なら：
     • 不一致が発生したのがパターンの先頭文字 (P[0]) の場合です。これは、テキストの現在の位置iからパターンを開始しても一致しなかったことを意味します。
     • この場合、パターンを1文字だけスライドさせて、テキストの次の位置から比較を開始する必要があります。
     • テキストのポインタiを1つ進めます。パターンのポインタjは0のままです。

このプロセスを擬似コードで表すと以下のようになります。

“`
Function KMPSearch(T, N, P, M):
Compute π = compute_prefix_function(P, M)

i = 0 // index for text T
j = 0 // index for pattern P

while i < N:
if P[j] == T[i]:
// Characters match, move to the next
i = i + 1
j = j + 1

if j == M:
  // Pattern found at text index (i - M)
  print "Pattern found at index", (i - M)
  // To find next occurrence, shift pattern using π table
  j = π[j - 1] 
  // Note: some implementations might just return here if only the first match is needed
  // or continue searching after finding a match

else if i < N and P[j] != T[i]:
  // Mismatch after j > 0 characters matched, or mismatch at j = 0
  if j != 0:
    // Use π table to shift pattern
    j = π[j - 1] 
    // Text pointer i remains the same
  else:
    // Mismatch at pattern index 0, just move text pointer
    i = i + 1
    // Pattern pointer j remains 0

“`

具体的な検索例：T = "ABABDABACDABABCABAB", P = "ABABCABAB"

テキスト T の長さ N = 19
パターン P の長さ M = 9

まずπ配列を計算します。P = "ABABCABAB"
* P[0]=”A”, π[0]=0
* P[0..1]=”AB”, π[1]=0
* P[0..2]=”ABA”, π[2]=1 (‘A’)
* P[0..3]=”ABAB”, π[3]=2 (‘AB’)
* P[0..4]=”ABABC”, π[4]=0
* P[0..5]=”ABabca”, π[5]=1 (‘a’) – 実際は’a’ではなく’A’でした。例を修正します。
* P[0..5]=”ABABCA“, π[5]=1 (‘A’) – P[5]は’C’なので、例を修正します。
* P[0..5]=”ABABCA” はパターンP=”ABABCABAB”にありません。例を再修正します。

正しいパターン P = "ABABCABAB" でπ配列を計算します。
* P[0]=”A”, π[0]=0
* P[0..1]=”AB”, π[1]=0
* P[0..2]=”ABA”, π[2]=1 (‘A’)
* P[0..3]=”ABAB”, π[3]=2 (‘AB’)
* P[0..4]=”ABABC”, π[4]=0
* P[0..5]=”ABabca”, π[5]=1 (‘a’) – P[5]は’A’でした。
* P[0..5]=”ABabca” -> P[0...5] = "ABabca" -> P[0..5] = "ABABCD"
* P = “ABABCABAB” M=9
* j=0 P[0]=’A’, π[0]=0, k=0
* j=1 P[1]=’B’, k=0, P[1]!=’P[0]’, π[1]=0, k=0
* j=2 P[2]=’A’, k=0, P[2]==’P[0]’, π[2]=1, k=1
* j=3 P[3]=’B’, k=1, P[3]==’P[1]’, π[3]=2, k=2
* j=4 P[4]=’C’, k=2, P[4]!=’P[2]’, k=π[1]=0, P[4]!=’P[0]’, π[4]=0, k=0
* j=5 P[5]=’A’, k=0, P[5]==’P[0]’, π[5]=1, k=1
* j=6 P[6]=’B’, k=1, P[6]==’P[1]’, π[6]=2, k=2
* j=7 P[7]=’A’, k=2, P[7]==’P[2]’, π[7]=3, k=3
* j=8 P[8]=’B’, k=3, P[8]==’P[3]’, π[8]=4, k=4

π配列は [0, 0, 1, 2, 0, 1, 2, 3, 4] となります。

検索処理：T = "ABABDABACDABABCABAB", P = "ABABCABAB", π = [0, 0, 1, 2, 0, 1, 2, 3, 4]

i=0, j=0: T[0]=’A’, P[0]=’A’. Match. i=1, j=1.
i=1, j=1: T[1]=’B’, P[1]=’B’. Match. i=2, j=2.
i=2, j=2: T[2]=’A’, P[2]=’A’. Match. i=3, j=3.
i=3, j=3: T[3]=’B’, P[3]=’B’. Match. i=4, j=4.
i=4, j=4: T[4]=’D’, P[4]=’C’. Mismatch. j=4 > 0. Shift using π[j-1] = π[3] = 2. j = 2. i remains 4.

T: A B A B D A B A C D A B A B C A B A B
P: A B A B C A B A B (i=0, j=0 -> i=4, j=4)
A B A B C A B A B (Shift. i=4, j becomes 2)

i=4, j=2: T[4]=’D’, P[2]=’A’. Mismatch. j=2 > 0. Shift using π[j-1] = π[1] = 0. j = 0. i remains 4.

T: A B A B D A B A C D A B A B C A B A B
P: A B A B C A B A B (i=4, j=2)
A B A B C A B A B (Shift. i=4, j becomes 0)

i=4, j=0: T[4]=’D’, P[0]=’A’. Mismatch. j=0. Increment i. i=5. j remains 0.

T: A B A B D A B A C D A B A B C A B A B
P: A B A B C A B A B (i=4, j=0)
A B A B C A B A B (i=5, j=0)

i=5, j=0: T[5]=’A’, P[0]=’A’. Match. i=6, j=1.
i=6, j=1: T[6]=’B’, P[1]=’B’. Match. i=7, j=2.
i=7, j=2: T[7]=’A’, P[2]=’A’. Match. i=8, j=3.
i=8, j=3: T[8]=’C’, P[3]=’B’. Mismatch. j=3 > 0. Shift using π[j-1] = π[2] = 1. j = 1. i remains 8.

T: A B A B D A B A C D A B A B C A B A B
P: A B A B C A B A B (i=5, j=0 -> i=8, j=3)
A B A B C A B A B (Shift. i=8, j becomes 1)

i=8, j=1: T[8]=’C’, P[1]=’B’. Mismatch. j=1 > 0. Shift using π[j-1] = π[0] = 0. j = 0. i remains 8.

T: A B A B D A B A C D A B A B C A B A B
P: A B A B C A B A B (i=8, j=1)
A B A B C A B A B (Shift. i=8, j becomes 0)

i=8, j=0: T[8]=’C’, P[0]=’A’. Mismatch. j=0. Increment i. i=9. j remains 0.
i=9, j=0: T[9]=’D’, P[0]=’A’. Mismatch. j=0. Increment i. i=10. j remains 0.
i=10, j=0: T[10]=’A’, P[0]=’A’. Match. i=11, j=1.
i=11, j=1: T[11]=’B’, P[1]=’B’. Match. i=12, j=2.
i=12, j=2: T[12]=’A’, P[2]=’A’. Match. i=13, j=3.
i=13, j=3: T[13]=’B’, P[3]=’B’. Match. i=14, j=4.
i=14, j=4: T[14]=’C’, P[4]=’C’. Match. i=15, j=5.
i=15, j=5: T[15]=’A’, P[5]=’A’. Match. i=16, j=6.
i=16, j=6: T[16]=’B’, P[6]=’B’. Match. i=17, j=7.
i=17, j=7: T[17]=’A’, P[7]=’A’. Match. i=18, j=8.
i=18, j=8: T[18]=’B’, P[8]=’B’. Match. i=19, j=9.

j == M (9に到達)！パターンが見つかりました。
見つかった位置は i - M = 19 - 9 = 10 です。
テキストのインデックス10 (T[10]) からパターンが始まっています。

発見後、検索を続ける場合：j = π[M-1] = π[8] = 4 となります。i は既に19です。i < N (19 < 19) は偽となり、ループが終了します。この例ではこれ以上マッチはありません。

この詳細な追跡から分かるように、不一致が発生した際に、KMPアルゴリズムはπ配列を使ってパターンのポインタjを巻き戻しますが、テキストのポインタiは決して巻き戻しません。iは常に前進するか、その場に留まるだけです（不一致時にj>0でjを更新する場合）。テキストを一度読んだ場所を繰り返し比較しないことが、KMPアルゴリズムの効率性の秘密です。

計算量解析

• 前処理（π配列計算）: 上記で示したように、このフェーズは O(M) の時間計算量で完了します。
• 検索処理: テキストのポインタ i は、j==0 で不一致が起きた場合や文字が一致した場合にのみ増加します。それ以外の場合 (j>0 で不一致) は、i はそのままに j が減少します。i は全体で N 回増加します。j は、一致時に最大 M まで増加し、不一致時に最大 M-1 まで減少します。j の総増加量は最大で N回（完全に一致する場合が N/M 回起こりうるため）と見なせます。j の減少は π[j-1] に基づきますが、この減少は k の総減少量と同様に O(M) に抑えられます。テキストの各文字はパターン上の各文字と比較される回数が限定されているため、検索処理全体の計算量は O(N + M) となります。

したがって、KMPアルゴリズム全体の時間計算量は O(N + M) です。これは、テキスト長 N とパターン長 M の線形和であり、ナイーブ法の最悪計算量 O(N * M) と比べて飛躍的に効率的です。特に N が M よりはるかに大きい場合や、パターンがテキスト中に繰り返し出現し、部分一致が多い場合に、KMPアルゴリズムの優位性が顕著になります。

KMPアルゴリズムのメリットと応用

KMPアルゴリズムは、その計算効率の高さから多くの場面で利用されています。ナイーブ法と比較した際の主なメリットと、代表的な応用例を以下に示します。

メリット

1. 高い効率性（線形時間計算量 O(N+M)）:

   • これがKMPアルゴリズム最大のメリットです。テキスト長Nとパターン長Mに対して、計算量が線形時間で済むため、大規模なデータに対しても高速に処理を行うことができます。
   • ナイーブ法の O(N*M) は、NやMが大きくなると加速度的に計算時間が増大するのに対し、KMPはN+Mに比例するため、スケールしてもパフォーマンス劣化が緩やかです。
   • 特に、パターンの内部構造に自己相関が多く含まれる場合（例: AAAA、ABABAB）、ナイーブ法は何度も後戻りして非効率になる傾向がありますが、KMPはその特性をπ配列として活用するため、非常に効率的に処理できます。

2. 無駄な再探索の削減:

   • ナイーブ法では、不一致が発生するたびにテキスト中の比較開始位置を戻してパターンの先頭から比較をやり直すことがありますが、KMPアルゴリズムではテキストのポインタiを後退させることがありません。これは、メモリへのアクセス効率や、テキストをストリームとして一度だけ読むようなアプリケーションにおいて有利に働きます。
   • 不一致時に既に一致していた部分の情報を最大限に活用し、次に比較すべき最適な位置へパターンをシフトすることで、不要な比較を徹底的に削減します。

3. 計算量の安定性:

   • KMPアルゴリズムは、最悪の場合でもO(N+M)という線形時間を保証します。ナイーブ法のように、特定の入力パターン（例: AAAAのような繰り返しが多いパターン）によってパフォーマンスが極端に悪化することがありません。常に安定した速度で検索を実行できるため、パフォーマンス予測が立てやすいという利点があります。

4. テキストを一度だけ読み込む（原則として）:

   • 基本的なKMPアルゴリズムは、テキストを先頭から順に一度だけスキャンする形で処理を進めます（例外は、不一致時にテキストポインタがその場に留まり、パターンポインタが移動するケース）。これは、テキストデータが非常に大きく、メモリに乗り切らない場合や、ストリームとして入力される場合に有利です。

応用例

KMPアルゴリズム、あるいはその概念を利用したアルゴリズムは、様々な分野で活用されています。

• テキストエディタやワープロソフトの「検索」機能: 巨大なファイルの中から特定の単語やフレーズを高速に探し出すのに適しています。
• プログラミング言語のコンパイラ/インタプリタ: ソースコードを字句解析する際に、キーワードや識別子などのパターンマッチングに利用されることがあります。
• バイオインフォマティクス: DNAやタンパク質の配列の中から特定の遺伝子配列やパターン（モチーフ）を検索する際に、KMPやその発展形（Aho-Corasick法など）が使われます。配列データは非常に長大になるため、効率的な検索アルゴリズムが不可欠です。
• ネットワークセキュリティ: 不正なパケットやマルウェアのシグネチャ（既知の悪意あるパターン）をネットワークトラフィックの中から検出する際に、高速なパターンマッチングが必要です。KMPやAho-Corasick法が応用されます。
• データ圧縮: 特定の繰り返しパターンを見つけ出すプロセスで、文字列検索アルゴリズムが補助的に利用されることがあります。
• 剽窃検出システム: 文書間で似たフレーズや文章パターンを比較・検出する際に、効率的な部分文字列検索が必要になります。

他の効率的な文字列検索アルゴリズムとの比較

KMPアルゴリズム以外にも、Rabin-Karp法（ハッシュを利用）、Boyer-Moore法（後方一致を利用）など、効率的な文字列検索アルゴリズムが存在します。

• Boyer-Moore法: 多くの場合、KMP法よりも高速に動作する傾向があります。これは、パターンの末尾から比較を開始し、不一致時にパターンを大きくシフトさせることができるためです。特に、パターンがテキスト中にほとんど出現しない場合や、アルファベットの種類が多い場合に効率的です。しかし、Boyer-Moore法の最悪計算量はナイーブ法と同じO(N*M)になるケースが存在します（ただし、実用上そのようなケースは稀です）。
• Rabin-Karp法: ローリングハッシュという技術を使って効率的に一致候補を見つけ出します。シンプルで実装しやすい一方、ハッシュの衝突による偽陽性の問題があり、完全に一致するかどうかの最終確認が必要です。平均的には高速ですが、最悪計算量はO(N*M)になる場合があります。

KMPアルゴリズムは、これらのアルゴリズムと比較して、常に線形時間 O(N+M) を保証するという点で優位性があります。どのような入力テキストやパターンに対しても、パフォーマンスが大きく劣化することはありません。そのため、最悪計算量の保証が重要な場面や、テキストをストリームとして処理する場合などに適しています。

KMPアルゴリズムの実装例 (Python)

KMPアルゴリズムの概念を理解したところで、Pythonでの実装例を見てみましょう。π配列を計算する関数と、そのπ配列を利用して文字列を検索する関数を記述します。

“`python
import sys

1. π配列（失敗関数）を計算する関数

M: パターンPの長さ

π: 計算結果を格納するリスト

def compute_prefix_function(P):
“””
パターンのπ配列（失敗関数）を計算する。
π[i]は、P[0…i]の最も長い、真の接頭辞でありかつ接尾辞である部分文字列の長さ。
“””
M = len(P)
π = [0] * M # π配列を初期化

k = 0  # kは現在の接頭辞/接尾辞一致の長さ
# π[0]は常に0なので、j=1から開始
for j in range(1, M):
    # k > 0 かつ P[j] != P[k] の間、kをπ[k-1]に更新
    # これは、より短い接頭辞/接尾辞一致を探す処理
    while k > 0 and P[j] != P[k]:
        k = π[k - 1]

    # P[j]とP[k]が一致した場合、kをインクリメント
    if P[j] == P[k]:
        k = k + 1

    # 現在の位置jにおけるπ値を記録
    π[j] = k

return π

2. KMPアルゴリズムによる文字列検索関数

T: テキスト文字列, N: テキストの長さ

P: パターン文字列, M: パターンの長さ

π: パターンPのπ配列

def kmp_search(T, P):
“””
KMPアルゴリズムを用いて、テキストTからパターンPを検索する。
パターンが見つかった全ての開始インデックスのリストを返す。
“””
N = len(T)
M = len(P)

# パターンのπ配列を計算（前処理）
π = compute_prefix_function(P)

occurrences = [] # 発見した位置を格納するリスト

i = 0  # テキストTの現在のインデックス
j = 0  # パターンPの現在のインデックス

while i < N:
    # 現在の文字が一致する場合
    if P[j] == T[i]:
        i = i + 1
        j = j + 1

    # パターン全体が一致した場合（発見）
    if j == M:
        # パターンがテキストのインデックス (i - M) から見つかった
        occurrences.append(i - M)
        # 次の出現を探すために、π配列を使ってパターンをシフト
        j = π[j - 1] # jをπ[M-1]に更新
        # iはそのまま（次のループでT[i]とP[j]が比較される）

    # 現在の文字が一致しない場合
    # j > 0 の場合、パターンポインタjをπ[j-1]に移動させる
    # j == 0 の場合、テキストポインタiを1つ進める
    elif i < N and P[j] != T[i]:
        # 不一致。j > 0 の場合はπ配列を使う。
        if j != 0:
            j = π[j - 1]
            # テキストポインタiはそのまま
        else:
            # j == 0 （パターンの先頭で不一致）。テキストポインタiを1つ進める。
            i = i + 1
            # パターンポインタjは0のまま

return occurrences

テスト用の例

if name == “main“:
text = “ABABDABACDABABCABAB”
pattern = “ABABCABAB”

print(f"テキスト: {text}")
print(f"パターン: {pattern}")

# π配列を計算して表示
pi_table = compute_prefix_function(pattern)
print(f"π配列: {pi_table}")

# KMP検索を実行
found_indices = kmp_search(text, pattern)

if found_indices:
    print(f"パターンが見つかったインデックス: {found_indices}")
    # 見つかった部分を表示
    for index in found_indices:
        print(f"  テキスト[{index}..{index+len(pattern)-1}]: {text[index : index+len(pattern)]}")
else:
    print("パターンは見つかりませんでした。")

print("-" * 20)

# 別のテスト例
text2 = "AAAAAAAAB"
pattern2 = "AAAAB"
print(f"テキスト: {text2}")
print(f"パターン: {pattern2}")
pi_table2 = compute_prefix_function(pattern2)
print(f"π配列: {pi_table2}")
found_indices2 = kmp_search(text2, pattern2)
if found_indices2:
    print(f"パターンが見つかったインデックス: {found_indices2}")
    for index in found_indices2:
        print(f"  テキスト[{index}..{index+len(pattern2)-1}]: {text2[index : index+len(pattern2)]}")
else:
    print("パターンは見つかりませんでした。")

print("-" * 20)

# 一致しない例
text3 = "ABCDEFG"
pattern3 = "XYZ"
print(f"テキスト: {text3}")
print(f"パターン: {pattern3}")
pi_table3 = compute_prefix_function(pattern3)
print(f"π配列: {pi_table3}")
found_indices3 = kmp_search(text3, pattern3)
if found_indices3:
    print(f"パターンが見つかったインデックス: {found_indices3}")
else:
    print("パターンは見つかりませんでした。")

“`

このPythonコードは、KMPアルゴリズムのπ配列計算と検索処理のロジックを直接的に実装しています。compute_prefix_function 関数がパターン文字列からπ配列を生成し、kmp_search 関数がそのπ配列を利用してテキスト内を検索します。テスト用の if __name__ == "__main__": ブロックでは、いくつかの例を使って関数の動作を確認できます。

コードを読む際は、変数 i と j の役割、そして不一致時に j = π[j-1] がどのように機能しているかに注目すると理解が深まります。j == M となった際に j = π[j-1] に更新しているのは、パターン全体が見つかった後も検索を続け、次の出現を探すためです。もし最初に見つかった一つだけを探せばよい場合は、発見時にループを終了させても構いません。

発展・関連アルゴリズム

KMPアルゴリズムは、文字列検索の分野における重要な基礎です。KMPの考え方を基にした、あるいは関連する他の効率的なアルゴリズムも存在します。

• Aho-Corasick法: KMPアルゴリズムは単一のパターンを検索するためのものですが、現実の世界では複数のパターンを同時に検索したいケースが多くあります（例: アンチウイルスソフトでの多数のウイルスシグネチャ検索）。Aho-Corasick法は、KMPの失敗関数の概念を拡張し、複数のパターンを効率的に検索するためのアルゴリズムです。検索対象の複数のパターンから状態遷移機械（オートマトン）を構築し、テキストを一度スキャンするだけで、出現する全てのパターンを見つけ出せます。計算量は O(N + 総パターン長 + 出現回数) となります。

• Boyer-Moore法: 前述の通り、多くの場面でKMPより高速な実効性能を示します。KMPがパターンの前方から比較を開始するのに対し、Boyer-Moore法は後方から比較を開始します。不一致時には、「悪い文字ルール (Bad Character Rule)」と「良い接尾辞ルール (Good Suffix Rule)」という2つのルールに基づいて、パターンを可能な限り大きくシフトさせます。これは、不一致が発生した文字や、その直前まで一致していた接尾辞の情報から、パターンを最低限どこまでシフトできるかを判断するものです。

• Rabin-Karp法: ハッシュ関数を利用して文字列比較を効率化するアルゴリズムです。テキストのウィンドウ（パターンと同じ長さの部分文字列）のハッシュ値を計算し、パターンのハッシュ値と比較します。ハッシュ値が一致した候補箇所でのみ、実際の文字列比較を行います。ハッシュ計算が効率的に行える場合（例: ローリングハッシュ）、平均的な計算量は低くなります。衝突が少ないハッシュ関数を選べば実用上高速ですが、最悪ケースではナイーブ法と同等の計算量になることがあります。

これらのアルゴリズムはそれぞれ異なるアプローチを取りますが、文字列検索の効率化という同じ目標を共有しています。KMPアルゴリズムで培った「パターンの構造を事前に解析する」「不一致時の再探索を減らす」といった考え方は、これらのアルゴリズムを理解する上でも役立ちます。

まとめ：KMPアルゴリズムの重要性

この記事では、文字列検索の基本的な手法であるナイーブ法が抱える非効率性の問題点を明確にし、それを克服するための強力なアルゴリズムである「KMPアルゴリズム」について詳細に解説しました。

KMPアルゴリズムの核心は、パターン文字列の自己相関を捉えた「プレフィックス関数（π配列、失敗関数）」にあります。この関数を検索の前処理として O(M) 時間で計算することで、検索中（O(N) 時間）に不一致が発生した場合でも、テキストの比較位置を戻すことなく、π配列を利用してパターンを適切にシフトさせることができます。

その結果、KMPアルゴリズムはテキスト長Nとパターン長Mに対して、常に線形時間 O(N + M) という非常に効率的な時間計算量を達成します。これは、ナイーブ法の最悪計算量 O(N * M) と比較して、特に大きな文字列を扱う際に圧倒的なパフォーマンス差となって現れます。

KMPアルゴリズムのメリットは、単に高速であるだけでなく、無駄な再探索をせず、テキストポインタを戻さない処理効率、そして最悪計算量が保証されていることによるパフォーマンスの安定性にあります。これらの特性から、KMPアルゴリズムは、テキストエディタ、バイオインフォマティクス、ネットワークセキュリティなど、様々な分野で広く応用されています。

KMPアルゴリズムの理解は、文字列検索という基本的ながら奥深い分野への入り口となります。この記事を通じて、KMPの仕組み、特にπ配列の役割とその計算方法、そしてそれを利用した検索処理のロジックを掴んでいただけたなら幸いです。さらに高速なBoyer-Moore法や、複数パターンに対応するAho-Corasick法など、関連するアルゴリズムへと学習を進める上でも、KMPの知識は強固な基盤となるでしょう。

効率的なアルゴリズムは、コンピュータサイエンスにおける知恵の結晶です。KMPアルゴリズムは、シンプルでありながらもエレガントなアイデアによって、実用的な問題を効率的に解決できることを示しています。ぜひ、実際にコードを動かしてみるなどして、KMPアルゴリズムの力を体感してみてください。

---