KMPアルゴリズムで学ぶパターンマッチングの高速化

1. はじめに：パターンマッチングの重要性と課題

現代のデジタル世界において、私たちは膨大な量のテキストデータに囲まれて生活しています。ウェブページの検索、ドキュメント内の特定のキーワードの探索、ソースコードの分析、DNA配列の照合、ネットワークパケットのフィルタリングなど、さまざまな場面で「ある大きなテキスト（検索対象文字列、テキスト）」の中に「ある特定の短い文字列（パターン）」が含まれているか、含まれているならばどこに含まれているか、といった問題を解決する必要があります。この問題は「パターンマッチング」または「文字列検索」と呼ばれ、情報科学における基本的な問題の一つです。

パターンマッチングは、一見単純な問題に見えますが、その効率性は処理速度に大きく影響します。特に、検索対象文字列が非常に長い場合や、パターンマッチングを繰り返し実行する必要がある場合、非効率なアルゴリズムはシステムの応答性を著しく低下させる可能性があります。例えば、巨大なログファイルから特定のエラーパターンを探す場合、あるいは大規模なデータベースから特定のキーワードを含むレコードを検索する場合など、効率的なパターンマッチングアルゴリズムの存在は不可欠です。

本記事では、パターンマッチング問題を効率的に解決する古典的かつ非常に洗練されたアルゴリズムである「KMPアルゴリズム」について、その詳細を徹底的に解説します。KMPアルゴリズムは、その独創的なアイデアにより、パターンマッチングを線形時間で行うことを可能にしました。これは、検索対象文字列の長さをN、パターンの長さをMとしたときに、計算量がO(N+M)となることを意味します。これは、多くの実用的な場面で十分高速な性能を発揮します。

まず、最も直感的でシンプルなパターンマッチングアルゴリズムを紹介し、その非効率性の原因を分析します。次に、KMPアルゴリズムの核となるアイデアと、それを実現するための重要な補助情報である「接頭辞関数（LPS配列）」について詳しく説明します。LPS配列の計算方法、KMP検索アルゴリズム本体、そしてその計算量解析を通して、KMPアルゴリズムがなぜ高速なのか、どのように機能するのかを深く理解していただけるでしょう。

2. 素朴なパターンマッチングアルゴリズム：シンプルさとその限界

パターンマッチングを考える上で、最も最初に思いつくであろうシンプルで直感的なアルゴリズムは、「素朴なアルゴリズム（Naive Algorithm）」と呼ばれるものです。このアルゴリズムは非常に分かりやすく実装も容易ですが、その効率性には大きな課題があります。

2.1 アルゴリズムの説明

素朴なアルゴリズムの基本的な考え方は以下の通りです。
検索対象文字列（text, 長さN）とパターン（pattern, 長さM）が与えられたとします。
1. textの先頭から、パターンと同じ長さの部分文字列を取り出します。
2. その部分文字列とpatternが完全に一致するか比較します。
3. もし一致すれば、そこでパターンが見つかったことになります。
4. もし一致しなければ、textから取り出す部分文字列の開始位置を1文字分後ろにずらし、再度比較を行います。
5. この操作を、textの末尾まで、つまりtextのN-M番目の文字を先頭とする部分文字列まで繰り返します。

より具体的にインデックスを使って説明しましょう。
textを T[0...N-1]、patternを P[0...M-1] とします。
– text中の現在の比較開始位置を示すインデックス i を、0 から N-M まで順番に増加させます。
– 各 i の位置で、textの T[i...i+M-1] という部分文字列と、patternの P[0...M-1] を文字ごとに比較します。
– 比較は、patternのインデックス j を 0 から M-1 まで増加させながら行います。
– T[i+j] と P[j] を比較し、一致するかぎり j を増やします。
– もし j が M に達した場合、つまり P[0] から P[M-1] のすべてが T[i] から T[i+M-1] と一致した場合は、textのインデックス i の位置でパターンが見つかったことになります。
– もし比較の途中で T[i+j] != P[j] となった場合、現在の開始位置 i ではパターンは一致しなかったと判断し、textの開始位置を i+1 にずらして（つまり i を1つ増やして）次の比較に進みます。

擬似コードで表すと以下のようになります。

pseudo function NaiveSearch(text, pattern): N = length(text) M = length(pattern) for i from 0 to N - M: // textの開始位置 j = 0 while j < M and text[i + j] == pattern[j]: // 文字ごとの比較 j = j + 1 if j == M: // pattern全体が一致した print "Pattern found at index", i // パターンが複数出現する場合も探すなら、ここに処理を追加し i を進める // ただし、シンプルバージョンでは最初の1つを見つけるか、全ての可能性を試す // 例：複数見つけるなら、i をそのまま進める // 一致しなかった場合 (whileループが j < M で終了した場合) // textの開始位置 i は for ループによって自動的に i+1 に進む

2.2 計算量分析：なぜ遅いのか？（最悪ケースの詳細な考察）

素朴なアルゴリズムは理解しやすい反面、効率性の点で大きな問題を抱えています。その計算量を分析してみましょう。計算量は、通常、比較演算の回数で評価されます。

外側の for ループは、i を 0 から N-M まで回します。これは最大で N-M+1 回繰り返されます。
内側の while ループは、各 i の位置でパターンとの比較を行います。最悪の場合、この while ループは M 回（つまりパターンのすべての文字）比較する可能性があります。

したがって、単純に考えると、外側ループが N-M+1 回、内側ループが最大 M 回なので、全体の計算量は O((N-M+1) * M)、おおよそ O(N*M) と見積もられます。

この O(N*M) という計算量は、特に N と M が大きい場合に問題となります。例えば、N = 10^6、M = 1000 の場合、比較回数は約 10^9 回となり、現代のコンピュータでも無視できない時間が必要です。

さらに、この O(N*M) の計算量が最も顕著に現れる「最悪ケース」について詳しく考えてみましょう。最悪ケースは、多くの比較を行ったにも関わらず一致しない、という状況が繰り返される場合に発生します。

典型的な最悪ケースは、textとpatternのほとんどの文字が一致するが、最後の1文字だけが異なる、という状況が繰り返し発生する場合です。

最悪ケースの例：
– text = “AAAAAAAAAA…” (N個の’A’)
– pattern = “AAAAAB” (M個の’A’ + ‘B’)

この場合、素朴なアルゴリズムの動作を見てみましょう。
1. i=0 (text[0...M-1]) と pattern を比較します。最初の M-1 文字 (‘AAAAA’) は一致しますが、text[M-1] (‘A’) と pattern[M-1] (‘B’) は一致しません。M-1 回の比較が行われた後、不一致が検出されます。
2. textの開始位置を i=1 にずらします (text[1...M])。再び最初の M-1 文字は一致し、最後の1文字で不一致となります。これも M-1 回の比較が必要です。
3. このパターンは、i が N-M になるまで繰り返されます。

各開始位置 i (0 から N-M まで) について、比較は M 回近く行われます（正確には、M-1回一致してM回目で不一致）。
したがって、全体の比較回数は約 (N-M+1) * (M-1) となり、これは O(N*M) です。
例えば N=100, M=10 で text = "AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAB", pattern = "AAAAAAAAAB" のような場合、ほとんど全ての比較が M 回近く行われ、O(N*M) に近い比較回数になります。

この最悪ケースの非効率性は、パターンマッチングが失敗した際に、textの比較開始位置をたった1文字だけずらして、またパターンの先頭から比較をやり直すという点にあります。素朴なアルゴリズムは、それまでの比較で得られた「textのこの部分とpatternのこの部分が一致した」という貴重な情報を完全に捨て去ってしまいます。

KMPアルゴリズムは、まさにこの「情報を捨ててしまう」という無駄をなくすことで、効率的なパターンマッチングを実現します。

3. KMPアルゴリズムへの導入：効率化の閃き

3.1 素朴なアプローチの問題点再確認

素朴なアルゴリズムの最も大きな問題点は、比較が失敗したときに、textのポインタ（i）を単純に1文字分戻し、patternのポインタ（j）を先頭に戻してしまうことです。

例：
text = “ABC ABCDAB ABCDABCDABDE”
pattern = “ABCDABD”

素朴なアルゴリズムで i=0 から検索を開始します。
text: A B C_ABCDAB_...
pattern: A B C D A B D
i=0, j=0: T[0]=’A’, P[0]=’A’ -> 一致 (j=1)
i=0, j=1: T[1]=’B’, P[1]=’B’ -> 一致 (j=2)
i=0, j=2: T[2]=’C’, P[2]=’C’ -> 一致 (j=3)
i=0, j=3: T[3]=’_’, P[3]=’D’ -> 不一致

ここで i=0 からの比較は失敗しました。素朴なアルゴリズムでは、textの開始位置を1つずらし、iを1にし、patternの比較位置 j を 0 に戻して、text[1] から再び pattern の先頭と比較を始めます。

text: _B C_ABCDAB_...
pattern: A B C D A B D
i=1, j=0: T[1]=’B’, P[0]=’A’ -> 不一致

すぐに不一致が検出され、i は 2 に進みます。

text: __C_ABCDAB_...
pattern: A B C D A B D
i=2, j=0: T[2]=’C’, P[0]=’A’ -> 不一致

すぐに不一致が検出され、i は 3 に進みます。

そして i=3 で、text[3...9] (“ABCDAB_”) と pattern (“ABCDABD”) を比較します。
text: ___ABCDAB_...
pattern: A B C D A B D
i=3, j=0: T[3]=’A’, P[0]=’A’ -> 一致 (j=1)
i=3, j=1: T[4]=’B’, P[1]=’B’ -> 一致 (j=2)
i=3, j=2: T[5]=’C’, P[2]=’C’ -> 一致 (j=3)
i=3, j=3: T[6]=’D’, P[3]=’D’ -> 一致 (j=4)
i=3, j=4: T[7]=’A’, P[4]=’A’ -> 一致 (j=5)
i=3, j=5: T[8]=’B’, P[5]=’B’ -> 一致 (j=6)
i=3, j=6: T[9]=’_’, P[6]=’D’ -> 不一致

ここで i=3 からの比較も失敗しました。素朴なアルゴリズムでは i を 4 に進め、j を 0 に戻して再び比較を始めます。

لاحظしてください。i=3 で比較を行っていた時、私たちはtextの T[3...8] (“ABCDAB”) と patternの P[0...5] (“ABCDAB”) が一致していることを知りました。この情報があれば、i を 4 にずらして text[4] から比較を始めるのは少し無駄であることに気づけます。なぜなら、patternは ‘A’ で始まりますが、text[4] は ‘B’ です。text[5] は ‘C’ です… text[7] は ‘D’ です。これらの位置で pattern の先頭 ‘A’ が一致する可能性はありません。
次に pattern が一致する可能性があるのは、textのインデックス i がどの位置の時でしょうか？
i=3 の比較で、T[3...8] (“ABCDAB”) が P[0...5] (“ABCDAB”) と一致しました。不一致は T[9] と P[6] で発生しました。
この状況は、textの T[3] から始まる部分が “ABCDAB” であり、その次に ‘E’ (T[9]) が続いているという状態です。そして、pattern は “ABCDABD” です。
patternの一部 “ABCDAB” が textの T[3] から始まって一致したのですから、次に pattern が全体として一致する可能性があるのは、この一致した “ABCDAB” の部分文字列が、pattern自身の「接頭辞（prefix）」であり、かつ「接尾辞（suffix）」でもあるような部分を持っている場合です。

pattern = “ABCDABD”
このパターンの中で、接頭辞かつ接尾辞であるような部分文字列を探します。
– 長さ1: ‘A’ (接頭辞) vs ‘D’ (接尾辞) -> 異なる
– 長さ2: ‘AB’ (接頭辞) vs ‘BD’ (接尾辞) -> 異なる
– 長さ3: ‘ABC’ (接頭辞) vs ‘ABD’ (接尾辞) -> 異なる
– 長さ4: ‘ABCD’ (接頭辞) vs ‘CABD’ (接尾辞) -> 異なる
– 長さ5: ‘ABCDA’ (接頭辞) vs ‘CDABD’ (接尾辞) -> 異なる
– 長さ6: ‘ABCDAB’ (接頭辞) vs ‘BCDABD’ (接尾辞) -> 異なる

あれ？このパターン “ABCDABD” 自体には、長さ1以上の共通する接頭辞・接尾辞がありません。
しかし、先ほどの例では i=3 で patternの P[0...5] (“ABCDAB”) が一致しました。
この一致した部分 P[0...5] = “ABCDAB” の中で、接頭辞かつ接尾辞である最長の部分は何でしょうか？
– ‘A’ (接頭辞) vs ‘B’ (接尾辞) -> 異なる
– ‘AB’ (接頭辞) vs ‘AB’ (接尾辞) -> 一致！長さ2
– ‘ABC’ (接頭辞) vs ‘DAB’ (接尾辞) -> 異なる
– ‘ABCD’ (接頭辞) vs ‘CDAB’ (接尾辞) -> 異なる
– ‘ABCDA’ (接頭辞) vs ‘BCDAB’ (接尾辞) -> 異なる

“ABCDAB” の最長の共通接頭辞・接尾辞は “AB” (長さ2) です。
これは何を意味するのでしょうか？

i=3 で patternの P[0...5] が textの T[3...8] と一致しました。
text: T[3] T[4] T[5] T[6] T[7] T[8] T[9]
A B C D A B E
pattern: P[0] P[1] P[2] P[3] P[4] P[5] P[6]
A B C D A B D

T[9] (‘E’) と P[6] (‘D’) で不一致が発生しました。
現在、textのインデックス i=3 と patternのインデックス j=6 (不一致が起きた文字の次のインデックス、つまり一致した最後の文字のインデックス+1) の状態です。
一致した部分 pattern[0...5] は “ABCDAB” です。この部分の最長の共通接頭辞・接尾辞は “AB” (長さ2) です。
これは、pattern[0...1] (“AB”) が pattern[4...5] (“AB”) と同じであるということです。
P[0] P[1] P[2] P[3] P[4] P[5]
A B C D A B

textの T[3...8] が P[0...5] と一致したということは、
T[3...8] = “ABCDAB” です。
そして pattern[0...5] の接尾辞 P[4...5] は “AB” です。
これが textの T[7...8] に対応します。
text[7...8] = “AB”

同時に、pattern[0...5] の接頭辞 P[0...1] は “AB” です。
この接頭辞 “AB” は patternの先頭部分です。
つまり、textの T[7...8] が patternの先頭 P[0...1] と一致している可能性があるということです。

text: A B C D A B E ...
T[3]...T[8]

pattern: A B C D A B D
P[0]...P[6]

T[3...8] == P[0...5] が一致した状態で、T[9] と P[6] が不一致でした。
私たちは T[7...8] が P[4...5] と同じであること、そして P[4...5] が P[0...1] と同じであることを知っています。
つまり T[7...8] は P[0...1] と同じ “AB” です。
したがって、次に pattern が一致する可能性がある位置は、patternの先頭 (“AB”) が textの T[7] から一致し始める位置です。
これは、元の textの比較開始位置 i=3 を、i=3 + (j - length of longest proper prefix which is also suffix) だけ進めた位置に相当します。
ここで j=6 でした。一致した部分 P[0...5] の最長の共通接頭辞・接尾辞の長さは 2 です。
つまり、次に比較を開始すべき textのインデックスは i = 3 + (6 - 2) = 3 + 4 = 7 です。
そして、textの T[7] から patternと比較を再開しますが、T[7...8] は pattern[0...1] と一致していることが保証されています。
したがって、patternの比較は P[2] から開始すれば良いのです。

これが KMP アルゴリズムの核心アイデアです。不一致が起きたとき、素朴なアルゴリズムのように textのポインタを戻すのではなく、一致したパターンの部分構造（接頭辞と接尾辞の関係）を利用して、patternのポインタを適切に「ジャンプ」させることで、textのポインタを戻さずに検索を続けるのです。これにより、textの各文字は最大でも定数回しか比較されないことになり、線形時間での検索が実現します。

3.2 KMPの基本思想：無駄な比較を省く

KMPアルゴリズム（Knuth-Morris-Pratt Algorithm）の基本思想は、パターンマッチングの際に不一致が発生した状況を最大限に活用することです。
素朴なアルゴリズムが非効率である原因は、不一致が発生した際に textのポインタを戻してパターンの先頭から比較を再開してしまう点にありました。
KMPは、この不一致が発生した時点までに「textのこの部分とpatternのこの接頭辞部分が一致している」という事実を知っています。この情報を使って、次に pattern の比較を開始すべき text の位置と、その位置で pattern のどこから比較を開始すべきかを賢く判断します。

具体的には、textの T[i...i+j-1] が patternの P[0...j-1] と一致し、T[i+j] と P[j] で不一致が発生したとします。
Text: ... T[i] ... T[i+j-1] T[i+j] ... Pattern: P[0] ... P[j-1] P[j] ... <--- j characters matched ---> ^ 불일치 위치
素朴なアルゴリズムは、ここで i を i+1 にして、j を 0 に戻します。
KMPは、textポインタ i を戻さず、patternポインタ j だけを戻します。しかし、単純に j を 0 に戻すのではなく、次に比較すべき patternの適切な位置 j' に戻します。

この適切な位置 j' は、「一致した部分 pattern[0...j-1] の最も長い（Proper）接頭辞であり、かつ接尾辞でもある部分の長さ」によって決定されます。
Proper接頭辞とは、文字列自身を含まない接頭辞のことです（例: “ABCD” のProper接頭辞は “”, “A”, “AB”, “ABC”）。Proper接尾辞も同様です。

もし、一致した部分 pattern[0...j-1] の最長の共通Proper接頭辞・接尾辞の長さが k であるとします。
これは、pattern[0...k-1] が pattern[j-k...j-1] と一致していることを意味します。
そして、text[i...i+j-1] が pattern[0...j-1] と一致しているのですから、text[i+j-k...i+j-1] は pattern[j-k...j-1] と同じであり、それは pattern[0...k-1] とも同じです。
つまり、text[i+j-k...i+j-1] は pattern[0...k-1] と一致していることが保証されます。

Text: ... T[i] ... T[i+j-k-1] [ T[i+j-k] ... T[i+j-1] ] T[i+j] ... Pattern: P[0] ... P[k-1] [ P[k] ... P[j-1] ] P[j] ... <--- k ---> <--- j-k ---> Same as [P[j-k]...P[j-1]] = [pattern[0...k-1]]
不一致が T[i+j] と P[j] で起きた時、私たちは既に text[i+j-k...i+j-1] が pattern[0...k-1] と一致していることを知っています。
これは、あたかも textの現在の位置 i を i+(j-k) だけ進めた (i' として i+j-k とする) 位置で、patternの P[0...k-1] までが一致した状態から検索を再開できることを意味します。
新しい比較開始位置 i' では、textの T[i'...i'+k-1] と patternの P[0...k-1] が一致しています。
次に比較すべきは text[i'+k] と pattern[k] ですが、現在の状態は text[i+j] と pattern[j] での不一致でした。
新しい開始位置 i' は i + (j-k) ですから、i'+k は i + (j-k) + k = i+j となります。
つまり、textのポインタはそのまま i+j を指したまま、patternのポインタを j から k に移動させれば良いのです。

“`
不一致時: T[i+j] != P[j]
一致済み部分: text[i…i+j-1] == pattern[0…j-1]
一致済み部分 pattern[0…j-1] の最長共通Proper接頭辞・接尾辞の長さ = k
pattern[0…k-1] == pattern[j-k…j-1]
text[i+j-k…i+j-1] == pattern[j-k…j-1] (∵text[i…i+j-1] == pattern[0…j-1])
∴ text[i+j-k…i+j-1] == pattern[0…k-1]

次にpatternが一致する可能性のある位置は、textのT[i+j-k]からpatternのP[0]を始める場合。
textの現在インデックスは i+j。
patternの現在インデックスは j。
textのインデックス i はそのまま維持 (i+j-k を計算して i を更新するのではなく、textの比較位置T[i+j]はそのまま)。
patternのインデックス j を k に更新する。
つまり、不一致が起きたら、patternのポインタを「一致した部分の最長共通Proper接頭辞・接尾辞の長さ」にジャンプさせる。
“`

この「一致した部分の最長共通Proper接頭辞・接尾辞の長さ」を効率的に知るための情報が、KMPアルゴリズムの鍵となる「接頭辞関数（Prefix Function）」または「失敗関数（Failure Function）」、一般的には「LPS配列（Longest Proper Prefix which is also Suffix）」と呼ばれるものです。

4. KMPアルゴリズムの要：接頭辞関数（LPS配列）

4.1 接頭辞と接尾辞

まず、基本的な用語を整理します。
文字列 S（長さ m）が与えられたとき：
– S の 接頭辞 (Prefix) とは、S の先頭から始まる任意の部分文字列です。
例: S = “ABCD”
接頭辞: “”, “A”, “AB”, “ABC”, “ABCD”
– S の 接尾辞 (Suffix) とは、S の末尾で終わる任意の部分文字列です。
例: S = “ABCD”
接尾辞: “”, “D”, “CD”, “BCD”, “ABCD”
– Proper 接頭辞 (Proper Prefix) とは、文字列 S 自身を含まない接頭辞です。
例: S = “ABCD”
Proper 接頭辞: “”, “A”, “AB”, “ABC”
– Proper 接尾辞 (Proper Suffix) とは、文字列 S 自身を含まない接尾辞です。
例: S = “ABCD”
Proper 接尾辞: “”, “D”, “CD”, “BCD”

4.2 LPS配列の定義：次に試すべき位置を決定する情報

LPS配列（Longest Proper Prefix which is also Suffix）は、KMPアルゴリズムにおいて、不一致が発生した際にパターンをどれだけシフト（ジャンプ）させるかを決定するための情報を提供します。
LPS配列は、パターン文字列 P に対して計算されます。パターンの長さを M とすると、LPS配列 lps は長さ M の整数配列 lps[0...M-1] となります。

lps[i] の値は、「パターン P の P[0...i] という接頭辞部分文字列において、最も長いProper接頭辞であり、かつ接尾辞でもある部分文字列の長さ」を格納します。

例：pattern = “ABABAA”
– i=0: P[0] = “A”
Proper接頭辞: “”
Proper接尾辞: “”
共通部分の最長長: 0
lps[0] = 0

i=1: P[0...1] = “AB”
Proper接頭辞: “”, “A”
Proper接尾辞: “”, “B”
共通部分: “”
共通部分の最長長: 0
lps[1] = 0
i=2: P[0...2] = “ABA”
Proper接頭辞: “”, “A”, “AB”
Proper接尾辞: “”, “A”, “BA”
共通部分: “A”
共通部分の最長長: 1
lps[2] = 1 (∵ “A” が共通)
i=3: P[0...3] = “ABAB”
Proper接頭辞: “”, “A”, “AB”, “ABA”
Proper接尾辞: “”, “B”, “AB”, “BAB”
共通部分: “AB”
共通部分の最長長: 2
lps[3] = 2 (∵ “AB” が共通)
i=4: P[0...4] = “ABABA”
Proper接頭辞: “”, “A”, “AB”, “ABA”, “ABAB”
Proper接尾辞: “”, “A”, “BA”, “ABA”, “BABA”
共通部分: “A”, “ABA”
共通部分の最長長: 3
lps[4] = 3 (∵ “ABA” が共通)
i=5: P[0...5] = “ABABAA”
Proper接頭辞: “”, “A”, “AB”, “ABA”, “ABAB”, “ABABA”
Proper接尾辞: “”, “A”, “AA”, “BAA”, “ABAA”, “BABAA”
共通部分: “A”
共通部分の最長長: 1
lps[5] = 1 (∵ “A” が共通)

したがって、パターン “ABABAA” に対する LPS 配列は [0, 0, 1, 2, 3, 1] となります。

LPS配列の値 lps[i] は、パターン P の P[0...i] という部分文字列の末尾で不一致が起きたときに、次にパターン P のどのインデックスから比較を再開すべきかを示唆します。
具体的には、P[0...i] の末尾 (インデックス i) の文字と text の文字が不一致だった場合、私たちは P[0...i-1] が text のある部分と一致したことを知っています。この P[0...i-1] の最長の共通Proper接頭辞・接尾辞の長さが lps[i-1] です。
もし不一致が P[j] の位置で起きた（つまり text[i] と pattern[j] が不一致で、それまで pattern[0...j-1] が一致していた）ならば、次に pattern の比較を再開すべき位置は lps[j-1] です。

例えば、textの T[...] と pattern[0...5] (“ABABAA”) が一致し、次に T[...] と pattern[6] で不一致が起きたとします。
このとき j=6 です。一致した部分は pattern[0...5] (“ABABAA”) です。
lps[5] は 1 です。これは “ABABAA” の最長の共通Proper接頭辞・接尾辞が “A” である（長さ1）ことを意味します。
次に pattern の比較を再開すべきインデックスは lps[6-1] = lps[5] = 1 です。
つまり、不一致が起きた位置の pattern インデックスが j ならば、次に比較を再開する pattern インデックスは lps[j-1] となります。
ただし、j=0 の位置で既に不一致が起きた場合は、パターンを1文字分シフトするしかないので、次の pattern インデックスは常に 0 となります。

4.3 LPS配列の計算アルゴリズム

LPS配列は、パターン文字列自身を使って線形時間で計算できます。これは、KMPアルゴリズムの前処理ステップとして行われます。パターンの長さを M とすると、LPS配列の計算は O(M) の時間計算量で行われます。

LPS配列 lps[0...M-1] を計算するアルゴリズムを考えます。
lps[i] は、P[0...i] の最長の共通Proper接頭辞・接尾辞の長さです。
lps[0] は常に 0 です（長さ1の文字列のProper接頭辞/接尾辞は空文字列のみ）。

lps[i] の値を計算する際に、既に計算済みの lps[0...i-1] の値を利用することができます。
これは、LPS配列の定義が文字列の接頭辞に関するものであるため、動的計画法のような考え方を利用できるからです。

lps 配列を lps[0...M-1] とし、初期値はすべて 0 とします。
計算には2つのポインタを使います。
– i: 現在 lps の値を計算しているインデックス (1 から M-1 まで進む)。つまり、文字列 P[0...i] を見ている。
– len: 現在見ている P[0...i-1] という部分文字列における、最も長い共通Proper接頭辞・接尾辞の長さ。この長さは、次に一致するかどうかを判定するために利用される。lps[i-1] に相当する。

アルゴリズムのステップ：
1. 長さ M の lps 配列を作成し、すべて 0 で初期化します。
2. ポインタ len を 0 に初期化します（lps[0] は常に 0）。
3. ポインタ i を 1 に初期化します（lps[0] は計算済み）。
4. i < M である限り、以下のループを繰り返します。
a. P[i] と P[len] を比較します。
b. もし P[i] == P[len] ならば：
– これは、P[0...len] が P[i-len...i] という P[0...i] の末尾と一致していることを意味し、さらに1文字拡張して P[0...len] と P[i-len...i] の共通部分の長さを1増やせるということです。
– len を 1 増加させます (len = len + 1)。
– lps[i] に新しい len の値を格納します (lps[i] = len)。
– i を 1 増加させて次のインデックスに進みます (i = i + 1)。
c. もし P[i] != P[len] ならば：
– P[i] と、現在の len に対応する接頭辞の次の文字 P[len] が一致しませんでした。
– これは、長さ len の共通接頭辞・接尾辞をこれ以上伸ばせないことを意味します。
– この場合、より短い共通接頭辞・接尾辞を探す必要があります。
– len が 0 でない場合 (len > 0)：
– 次に試すべき共通接頭辞・接尾辞の長さは、現在の len-1 に対応する P[0...len-1] という部分文字列の最長の共通Proper接頭辞・接尾辞の長さです。
– この長さは lps[len-1] に格納されています。
– したがって、len を lps[len-1] に更新します。これは、P[i] と P[lps[len-1]] を比較することを意味します（i はそのまま）。
– len が 0 の場合 (len == 0)：
– これは、P[0...i] の中で、長さ1以上の共通Proper接頭辞・接尾辞が存在しないことを意味します。
– lps[i] は 0 のままです (lps[i] = 0)。
– i を 1 増加させて次のインデックスに進みます (i = i + 1)。

このアルゴリズムは、文字列 P[0...i] の LPS 値 lps[i] を計算する際に、既に計算済みの lps[0...i-1] の情報、特に lps[len-1] の値を利用している点に注目してください。len は常に、現在見ている P[0...i] の接頭辞 P[0...len-1] が、その接尾辞 P[i-len...i-1] と一致しているときの、その共通の長さを示しています。不一致が起きたら、この len の値を lps[len-1] に巻き戻すことで、より短い、しかし確実に接尾辞として一致する部分（そしてそれはパターン自身のより短い接頭辞に対応する部分）を探しに行きます。

4.3.2 LPS配列計算の具体例

例：pattern = “ABABAA” (M=6)
lps 配列を [0, 0, 0, 0, 0, 0] で初期化。 len = 0, i = 1。

i = 1: P[1] (‘B’) と P[len] (P[0], ‘A’) を比較。'B' != 'A'。
len は 0 なので、lps[1] = 0。 i を 1 増やして i = 2。 len は 0 のまま。
lps = [0, 0, 0, 0, 0, 0]
i = 2: P[2] (‘A’) と P[len] (P[0], ‘A’) を比較。'A' == 'A'。
一致。len を 1 増やして len = 1。 lps[2] = len (lps[2]=1)。 i を 1 増やして i = 3。
lps = [0, 0, 1, 0, 0, 0]
i = 3: P[3] (‘B’) と P[len] (P[1], ‘B’) を比較。'B' == 'B'。
一致。len を 1 増やして len = 2。 lps[3] = len (lps[3]=2)。 i を 1 増やして i = 4。
lps = [0, 0, 1, 2, 0, 0]
i = 4: P[4] (‘A’) と P[len] (P[2], ‘A’) を比較。'A' == 'A'。
一致。len を 1 増やして len = 3。 lps[4] = len (lps[4]=3)。 i を 1 増やして i = 5。
lps = [0, 0, 1, 2, 3, 0]
i = 5: P[5] (‘A’) と P[len] (P[3], ‘B’) を比較。'A' != 'B'。
不一致。len は 0 でない (len=3)。len を lps[len-1] (lps[3-1]=lps[2]=1) に更新。len = 1。 i はそのまま。
(現在 i=5, len=1)
i = 5: P[5] (‘A’) と P[len] (P[1], ‘B’) を比較。'A' != 'B'。
不一致。len は 0 でない (len=1)。len を lps[len-1] (lps[1-1]=lps[0]=0) に更新。len = 0。 i はそのまま。
(現在 i=5, len=0)
i = 5: P[5] (‘A’) と P[len] (P[0], ‘A’) を比較。'A' == 'A'。
一致。len を 1 増やして len = 1。 lps[5] = len (lps[5]=1)。 i を 1 増やして i = 6。
lps = [0, 0, 1, 2, 3, 1]
i = 6: i < M (6 < 6) は偽。ループ終了。

最終的な LPS 配列は [0, 0, 1, 2, 3, 1] となります。これは手計算の結果と一致します。

もう一つ例を見てみましょう。
例：pattern = “AAAA” (M=4)
lps 配列を [0, 0, 0, 0] で初期化。 len = 0, i = 1。

i = 1: P[1] (‘A’) と P[len] (P[0], ‘A’) を比較。'A' == 'A'。
一致。len = 1, lps[1] = 1, i = 2。
lps = [0, 1, 0, 0]
i = 2: P[2] (‘A’) と P[len] (P[1], ‘A’) を比較。'A' == 'A'。
一致。len = 2, lps[2] = 2, i = 3。
lps = [0, 1, 2, 0]
i = 3: P[3] (‘A’) と P[len] (P[2], ‘A’) を比較。'A' == 'A'。
一致。len = 3, lps[3] = 3, i = 4。
lps = [0, 1, 2, 3]
i = 4: i < M (4 < 4) は偽。ループ終了。

最終的な LPS 配列は [0, 1, 2, 3] となります。これも正しい結果です。

例：pattern = “ABCDE” (M=5)
lps 配列を [0, 0, 0, 0, 0] で初期化。 len = 0, i = 1。

i = 1: P[1] (‘B’) と P[len] (P[0], ‘A’) を比較。'B' != 'A'。
len は 0 なので、lps[1] = 0。 i = 2, len = 0。
lps = [0, 0, 0, 0, 0]
i = 2: P[2] (‘C’) と P[len] (P[0], ‘A’) を比較。'C' != 'A'。
len は 0 なので、lps[2] = 0。 i = 3, len = 0。
lps = [0, 0, 0, 0, 0]
i = 3: P[3] (‘D’) と P[len] (P[0], ‘A’) を比較。'D' != 'A'。
len は 0 なので、lps[3] = 0。 i = 4, len = 0。
lps = [0, 0, 0, 0, 0]
i = 4: P[4] (‘E’) と P[len] (P[0], ‘A’) を比較。'E' != 'A'。
len は 0 なので、lps[4] = 0。 i = 5, len = 0。
lps = [0, 0, 0, 0, 0]
i = 5: i < M (5 < 5) は偽。ループ終了。

最終的な LPS 配列は [0, 0, 0, 0, 0] となります。これも正しいです。アルファベットが全て異なる文字列の場合、長さ1以上の共通接頭辞・接尾辞は存在しないため、LPS配列はすべて0になります。

4.3.3 LPS配列計算アルゴリズムの計算量分析

LPS配列の計算アルゴリズムの時間計算量を分析します。
外側の while ループは i が 1 から M-1 まで増加するため、合計 M-1 回繰り返されます。
ループの各繰り返しにおいて、以下のいずれかの処理が行われます。
1. P[i] == P[len] の場合: i と len が両方とも1増加します。
2. P[i] != P[len] で len > 0 の場合: i はそのまま、len は lps[len-1] に減少します。lps[len-1] は常に len-1 以下です。
3. P[i] != P[len] で len == 0 の場合: i だけが1増加します。

注目すべきは、i は常に増加するか維持され、最終的に M に達してループが終了することです。i は最大で M 回増加します。
len は増加するか、または lps[len-1] の値に減少します。len が増加するのは P[i] == P[len] の場合のみで、このとき i も増加します。len が減少するのは P[i] != P[len] かつ len > 0 の場合です。

このアルゴリズムの計算量を考える際に、「ポインタの動き」を追跡することが有効です。
i は 0 から M-1 まで、合計 M 回インクリメントされます。i のデクリメントはありません。
len は 0 から始まり、最大で M-1 まで増加します。len が増加するのは P[i] == P[len] のときで、このとき i も増加します。len が減少するのは P[i] != P[len] かつ len > 0 のときで、このとき i は維持されます。
len が lps[len-1] に減少する操作は、len の現在の値を len-1 以下に減らすことになります。len は 0 より小さくなることはありません。
len が増加できる回数は、最大で M-1 回です（len が 0 から M-1 になるまで）。
i が増加できる回数は、最大で M 回です。
len が減少する回数はどうでしょうか？ len が1回増加するたびに、最大で1回減少操作（len = lps[len-1]）が行われる可能性があります。しかし、len が減少するたびに、その値はそれまでの最大値から必ず減少します。len は M-1 までしか増えないため、減少操作が際限なく繰り返されることはありません。

より厳密に考えると、i は M 回増加し、各ステップで i は少なくとも1回は増加するか、または len が減少します。
– P[i] == P[len] の場合: i が増加し、len が増加します。
– P[i] != P[len] かつ len > 0 の場合: i は維持され、len が減少します。
– P[i] != P[len] かつ len == 0 の場合: i が増加し、len は 0 のままです。

i が増加するステップの合計は M です。
len が減少するステップでは i は維持されます。len は 0 から始まり、最大 M-1 になります。len が +1 される回数の合計は最大 M-1 です。len が -k (k>=1) される操作は、len の値が lps[len-1] にセットされることを意味します。
len は全体を通して、i が進むにつれて増加と減少を繰り返しますが、その増加の総量は限られています（最大 M-1）。そして、len が減少する操作1回につき、len の値は必ず小さくなります。

実は、このアルゴリズムの全体的な計算量は O(M) であることが証明できます。i は M-1 までしか進まず、各ステップでは i が進むか len が戻るかのいずれかです。i が進むのは M 回。len が戻る操作は、len の値を lps[len-1] に設定しますが、lps[len-1] < len なので len は減少します。len の値は非負であり、最大で M-1 です。len の増加の総量は最大 M-1 であり、len の減少の総量は、増加の総量を超えることはありません。したがって、len が戻る操作の回数も O(M) 回に限定されます。
これにより、LPS配列の計算にかかる時間計算量は O(M) となります。空間計算量は、LPS配列を格納するための O(M) となります。

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

LPS配列 lps がパターン pattern に対して計算された後、いよいよ KMP 検索アルゴリズムを用いて、検索対象文字列 text の中に pattern が出現するかどうかを高速に調べます。
text の長さを N、pattern の長さを M とします。

KMP 検索アルゴリズムも、素朴なアルゴリズムと同様に2つのポインタを使用します。
– i: text の現在の文字を指すインデックス (0 から N-1 まで進む)。
– j: pattern の現在の文字を指すインデックス (0 から M-1 まで進む)。

アルゴリズムのステップ：
1. ポインタ i を 0 に初期化します（text の先頭）。
2. ポインタ j を 0 に初期化します（pattern の先頭）。
3. i < N である限り、以下のループを繰り返します。
a. text[i] と pattern[j] を比較します。
b. もし text[i] == pattern[j] ならば：
– 現在の文字は一致しました。次の文字の比較に進みます。
– i を 1 増加させます (i = i + 1)。
– j を 1 増加させます (j = j + 1)。
c. もし j == M ならば：
– pattern の全ての文字が一致しました。パターンが text のインデックス i-j の位置で見つかりました。
– この出現位置を記録します。
– パターン全体の次の出現位置を探すために、pattern のポインタ j を lps[j-1] に更新します。これにより、見つかったパターンの末尾部分の共通接頭辞・接尾辞を利用して、text ポインタ i を戻さずに次の検索を効率的に開始できます。(i はすでにパターンが見つかった位置の次を指しているので、そのままです)
d. もし text[i] != pattern[j] ならば：
– 不一致が発生しました。素朴なアルゴリズムと異なり、text のポインタ i は戻しません。
– pattern のポインタ j を更新します。
– もし j が 0 でない場合 (j > 0)：
– 不一致が起きたのは pattern の j 番目の文字です。これは、pattern[0...j-1] が text のある部分と一致した後に起きました。
– 次に比較を再開すべき pattern の位置は、一致した部分 pattern[0...j-1] の最長の共通Proper接頭辞・接尾辞の長さ lps[j-1] です。
– したがって、j を lps[j-1] に更新します。text[i] と pattern[lps[j-1]] を比較することになります。
– もし j が 0 の場合 (j == 0)：
– text[i] と pattern[0] の比較で最初から不一致でした。これは、text[i] の位置で pattern の先頭が一致しないことを意味します。
– pattern を1文字分シフトするしかありません。text の次の文字に進んで、pattern の先頭 (pattern[0]) と比較をやり直します。
– したがって、i を 1 増加させます (i = i + 1)。j は 0 のままです。

擬似コード：

“`pseudo
function KMPSearch(text, pattern, lps):
N = length(text)
M = length(pattern)
i = 0 // textのインデックス
j = 0 // patternのインデックス

while i < N:
if pattern[j] == text[i]:
i = i + 1
j = j + 1

if j == M:
  print "Pattern found at index", i - j
  // 複数の出現位置を探す場合:
  // 次の可能性は pattern[lps[j-1]...M-1] が text[i - (M-lps[j-1]) ... i-1] に一致すること
  // patternのポインタ j を lps[j-1] に更新
  j = lps[j - 1]
  // 単一の出現位置を見つけるだけで良いなら、ここで return や break

else if i < N and pattern[j] != text[i]:
  // 不一致発生
  if j != 0:
    // patternのポインタを巻き戻す
    // lps[j-1]は、一致した pattern[0...j-1] の最長の共通Proper接頭辞・接尾辞の長さ
    // 次に text[i] と比較すべきは pattern[lps[j-1]]
    j = lps[j - 1]
  else:
    // patternの先頭 (j=0) で不一致 -> textの次の文字へ
    i = i + 1

“`

5.2 KMP検索の具体例（詳細なステップ追跡）

例：
text = “ABC ABCDAB ABCDABCDABDE” (N=23)
pattern = “ABCDABD” (M=7)
LPS配列（事前に計算済）：lps = [0, 0, 0, 0, 1, 2, 0] (計算方法は4.3.2の例を参照)

初期状態: i=0, j=0

i=0, j=0: text[0] (‘A’) == pattern[0] (‘A’) -> 一致。i=1, j=1。
i=1, j=1: text[1] (‘B’) == pattern[1] (‘B’) -> 一致。i=2, j=2。
i=2, j=2: text[2] (‘C’) == pattern[2] (‘C’) -> 一致。i=3, j=3。
i=3, j=3: text[3] (‘ ‘) != pattern[3] (‘D’) -> 不一致。
j は 0 でない (j=3)。j を lps[j-1] (lps[2]=0) に更新。j=0。
i はそのまま (i=3)。
i=3, j=0: text[3] (‘ ‘) != pattern[0] (‘A’) -> 不一致。
j は 0 (j=0)。i を 1 増やす。i=4。j は 0 のまま。
i=4, j=0: text[4] (‘A’) == pattern[0] (‘A’) -> 一致。i=5, j=1。
i=5, j=1: text[5] (‘B’) == pattern[1] (‘B’) -> 一致。i=6, j=2。
i=6, j=2: text[6] (‘C’) == pattern[2] (‘C’) -> 一致。i=7, j=3。
i=7, j=3: text[7] (‘D’) == pattern[3] (‘D’) -> 一致。i=8, j=4。
i=8, j=4: text[8] (‘A’) == pattern[4] (‘A’) -> 一致。i=9, j=5。
i=9, j=5: text[9] (‘B’) == pattern[5] (‘B’) -> 一致。i=10, j=6。
i=10, j=6: text[10] (‘ ‘) != pattern[6] (‘D’) -> 不一致。
j は 0 でない (j=6)。j を lps[j-1] (lps[5]=2) に更新。j=2。
i はそのまま (i=10)。
i=10, j=2: text[10] (‘ ‘) != pattern[2] (‘C’) -> 不一致。
j は 0 でない (j=2)。j を lps[j-1] (lps[1]=0) に更新。j=0。
i はそのまま (i=10)。
i=10, j=0: text[10] (‘ ‘) != pattern[0] (‘A’) -> 不一致。
j は 0 (j=0)。i を 1 増やす。i=11。j は 0 のまま。
i=11, j=0: text[11] (‘A’) == pattern[0] (‘A’) -> 一致。i=12, j=1。
i=12, j=1: text[12] (‘B’) == pattern[1] (‘B’) -> 一致。i=13, j=2。
i=13, j=2: text[13] (‘C’) == pattern[2] (‘C’) -> 一致。i=14, j=3。
i=14, j=3: text[14] (‘D’) == pattern[3] (‘D’) -> 一致。i=15, j=4。
i=15, j=4: text[15] (‘A’) == pattern[4] (‘A’) -> 一致。i=16, j=5。
i=16, j=5: text[16] (‘B’) == pattern[5] (‘B’) -> 一致。i=17, j=6。
i=17, j=6: text[17] (‘D’) == pattern[6] (‘D’) -> 一致。i=18, j=7。
j == M (7 == 7) が真。パターンが text の i-j (18-7=11) の位置で見つかりました！
出現位置: 11。
複数の出現を探すため、j を lps[j-1] (lps[6]=0) に更新。j=0。
i はそのまま (i=18)。
i=18, j=0: text[18] (‘A’) == pattern[0] (‘A’) -> 一致。i=19, j=1。
i=19, j=1: text[19] (‘B’) == pattern[1] (‘B’) -> 一致。i=20, j=2。
i=20, j=2: text[20] (‘D’) != pattern[2] (‘C’) -> 不一致。
j は 0 でない (j=2)。j を lps[j-1] (lps[1]=0) に更新。j=0。
i はそのまま (i=20)。
i=20, j=0: text[20] (‘D’) != pattern[0] (‘A’) -> 不一致。
j は 0 (j=0)。i を 1 増やす。i=21。j は 0 のまま。
i=21, j=0: text[21] (‘E’) != pattern[0] (‘A’) -> 不一致。
j は 0 (j=0)。i を 1 増やす。i=22。j は 0 のまま。
i=22, j=0: text[22] (‘\0’ または終端) (i < N は 22 < 23 で真) と pattern[0] (‘A’) を比較…
text[22] は’E’の次の文字、実際には存在しない（あるいは末尾）。仮に N=23 の最後が ‘E’ とすると、ループは i=23 で終了する。
i=22 (textの最後の’E’のインデックス)、j=0 の状態。text[22] (‘E’) != pattern[0] (‘A’)。
j は 0 なので、i を 1 増やす。i=23。j は 0 のまま。
i < N (23 < 23) は偽。ループ終了。

検索が完了し、パターンはインデックス 11 で見つかりました。

このトレースを見ると、text のポインタ i は決して後戻りしていないことが分かります。不一致が起きた際、pattern のポインタ j は lps[j-1] に戻るだけです。これにより、不要な比較がスキップされ、効率的な検索が実現されています。

5.3 KMP検索アルゴリズムの計算量分析：線形時間の達成

KMP検索アルゴリズムの時間計算量を分析します。
検索は while i < N のループで行われます。
ループの各ステップでは、以下のいずれかが起こります。
1. text[i] == pattern[j] の場合: i と j が両方とも1増加します。
2. j == M （パターン一致）の場合: i は維持され、j は lps[j-1] に減少します。lps[j-1] は常に j-1 以下です。
3. text[i] != pattern[j] かつ j > 0 の場合: i は維持され、j は lps[j-1] に減少します。lps[j-1] は常に j-1 以下です。
4. text[i] != pattern[j] かつ j == 0 の場合: i だけが1増加します。j は 0 のままです。

ポインタ i は 0 から N まで、合計 N 回増加します（ケース1とケース4）。i は決して減少しません。したがって、ケース1とケース4の合計発生回数は N 回です。
ポインタ j は 0 から M まで増加し、0 以上の値に減少します。
j が増加するのはケース1のみです。j の最大値は M です。したがって、j が +1 される回数の合計は、パターン一致が複数回ある場合でも、i が進む中で j も進む回数の合計であり、i が最大 N 回進むことを考えると、j が M に到達する回数（パターンが見つかる回数）も考慮して、j の増加の総量は O(N) となります（具体的には N には依存しますが、O(N) に収まります）。

j が減少するのはケース2とケース3です。j が減少する操作 (j = lps[j-1]) は、j の値を j-1 以下に減らすことになります。j は非負であり、最大値は M です。j の増加の総量が O(N) であることから、j の減少の総量も O(N) に制限されます。
各ステップの計算量は定数時間です（比較、インデックス更新、配列参照など）。
全体のステップ数は、i が増加する回数（O(N)）と j が減少する回数（O(N)）の合計に比例します。
したがって、KMP 検索アルゴリズムの時間計算量は O(N) となります。

LPS配列の計算は O(M) でした。KMP検索アルゴリズム本体は O(N) です。
全体の時間計算量は、LPS配列の計算と検索アルゴリズム本体の合計となるため、O(M + N) となります。
これは、検索対象文字列の長さ N とパターンの長さ M に対して線形時間であり、非常に高速です。

空間計算量については、LPS配列を格納するために O(M) の空間が必要です。これはパターンマッチングのアルゴリズムとしては比較的小さい空間量です。

6. KMPアルゴリズムの全体的な計算量と特性

6.1 時間計算量：O(N+M)

KMPアルゴリズムの全体的な時間計算量は、LPS配列の計算にかかる時間 O(M) と、実際の検索にかかる時間 O(N) の合計であり、O(N+M) となります。
ここで N は検索対象文字列の長さ、M はパターンの長さです。
これは非常に優れた計算量であり、文字列検索アルゴリズムの理論的な下限（線形時間）を達成しています。これは、検索対象文字列の各文字とパターンの各文字を最低1回は見なければならないためです。

6.2 空間計算量：O(M)

KMPアルゴリズムは、LPS配列を格納するためにパターンの長さに比例する追加の空間が必要です。したがって、空間計算量は O(M) となります。
これは、検索対象文字列の長さに依存しないため、非常に長いテキストを検索する場合でもメモリ使用量はパターンの長さにのみ依存します。

6.3 KMPアルゴリズムの利点

高速性: 時間計算量が線形 (O(N+M)) であるため、特に検索対象文字列が長い場合に非常に高速です。素朴なアルゴリズムの最悪ケース O(N*M) と比較すると、その差は歴然です。
効率的なテキスト走査: 検索対象文字列のポインタを一切戻しません。これは、ストリーム処理（データが順番にしか読み込めない場合）など、テキストを一度に全てメモリにロードできない場合や、一方通行の読み込みしかできないデバイスからの入力処理に特に適しています。
保証された線形時間: 素朴なアルゴリズムとは異なり、特定の入力（例: 繰り返しの多い文字列）に対する最悪ケースでも線形時間性能を維持します。

6.4 KMPアルゴリズムの欠点

前処理の必要性: 検索を開始する前に、パターンに対してLPS配列を計算する必要があります。これは O(M) の時間がかかります。パターンが頻繁に変わるようなアプリケーションでは、この前処理のコストが無視できない場合があります。しかし、同じパターンで複数のテキストを検索する場合や、パターンが固定されている場合には、この前処理コストは全体の効率に大きく影響しません。
概念の複雑さ: 素朴なアルゴリズムに比べて、LPS配列の概念とその計算、および検索アルゴリズムにおけるLPS配列の使用法が直感的ではないため、理解や実装がやや難しいと感じられることがあります。

7. 他の高速パターンマッチングアルゴリズムとの比較

パターンマッチング問題に対しては、KMPアルゴリズム以外にも様々な高速なアルゴリズムが存在します。代表的なものに Boyer-Moore アルゴリズムや Rabin-Karp アルゴリズムがあります。簡単にKMPと比較してみましょう。

7.1 Boyer-Mooreアルゴリズム

Boyer-Moore アルゴリズムは、多くのテキスト処理システムで実際に使用されている、KMP と並んで有名な高速アルゴリズムです。
– 比較方向: KMP がパターンの先頭からテキストと比較していくのに対し、Boyer-Moore はパターンの末尾からテキストと比較を開始します。
– シフト量: Boyer-Moore は、不一致が発生した文字と、パターンの構造に基づいて、より大きなシフト量を計算するヒューリスティックを使用します（Bad Character Rule と Good Suffix Rule）。これにより、素朴なアルゴリズムや KMP よりも平均的に高速になる傾向があります。特に、アルファベットサイズが大きい場合に有効です。
– 最悪計算量: 標準的な Boyer-Moore アルゴリズムの最悪計算量は O(N*M) ですが、改良版（例: Boyer-Moore-Horspool, Sunday など）や理論的な改良版 (例: Boyer-Moore with Galil rule) では線形時間 O(N+M) を達成します。
– テキストポインタ: Boyer-Moore は不一致時にテキストポインタを戻す可能性があります。これは、KMP との大きな違いであり、ストリーム処理には KMP の方が適している場合があります。

7.2 Rabin-Karpアルゴリズム

Rabin-Karp アルゴリズムは、ハッシュ関数を利用した確率的なアルゴリズムです。
– 原理: テキストの固定長のウィンドウとパターンのハッシュ値を比較することで、一致の候補を効率的に絞り込みます。ハッシュ値が一致した場合のみ、実際の文字比較を行います。
– 平均計算量: 平均的には O(N+M) で動作します。
– 最悪計算量: 悪いハッシュ関数を用いた場合や、ハッシュ衝突が多く発生する入力に対しては、最悪 O(N*M) になる可能性があります。強力なハッシュ関数や複数のハッシュ関数を用いることで、この問題を緩和できます。
– 応用: 特定の文字列検索よりも、複数のパターンを同時に検索する場合や、最長共通部分文字列問題などに応用されることがあります。

7.3 KMPの立ち位置

KMPアルゴリズムは、常に線形時間 O(N+M) を保証するという点で優れています。テキストポインタを戻さないという特性も、特定のアプリケーション（ストリーム処理など）で重要な利点となります。Boyer-Moore が平均的に速いことが多い一方、KMP は最悪ケースでも性能が劣化しないという信頼性があります。Rabin-Karp はハッシュ衝突の問題がありますが、複数のパターン検索には効率的な場合があります。

どのアルゴリズムを選択するかは、アプリケーションの要件（テキストのサイズ、パターンの頻繁な変更、ストリーム処理の必要性、平均的な性能 vs 最悪ケース性能の保証など）に依存します。しかし、KMPアルゴリズムは、その理論的な美しさと線形時間保証という強力な特性から、文字列アルゴリズムを学ぶ上で非常に重要な位置を占めています。

8. KMPアルゴリズムの応用例

KMPアルゴリズムは、その効率性から様々な分野で応用されています。

8.1 テキストエディタや検索ツール

最も身近な応用例は、テキストエディタやコマンドラインツールでの文字列検索機能です。grep コマンドのようなツールは、内部的に KMP や Boyer-Moore のような高速なアルゴリズムを用いて、巨大なファイルから特定のパターンを含む行を高速に検索します。エディタでの「検索・置換」機能も、効率的なパターンマッチングアルゴリズムに依存しています。

8.2 DNA配列分析

生物学において、DNA やタンパク質の配列の中から特定の短い配列（モチーフ）を探すことは重要な問題です。これらの配列は非常に長くなることがあり、高速なパターンマッチングアルゴリズムが不可欠です。KMPアルゴリズムは、DNA配列のような文字列データにおける特定のサブ配列の検索に利用されます。

8.3 ネットワークパケット検査

ネットワークセキュリティにおいて、通過するパケットのペイロードから悪意のあるパターン（マルウェアのシグネチャなど）を検出するディープパケットインスペクション（DPI）が行われます。パケットはストリームとして到着することが多く、また低遅延が求められるため、テキストポインタを戻さずに線形時間で処理できる KMP アルゴリズムは、このようなリアルタイム処理に適した候補の一つとなります。

9. まとめ：KMPアルゴリズムが示す効率化の哲学

KMPアルゴリズムは、文字列パターンマッチング問題に対する非常に効果的な解決策であり、計算量の観点から理論的な限界である線形時間を達成しています。その核心にあるアイデアは、素朴なアルゴリズムの非効率性、すなわち不一致が発生した際にそれまでの貴重な比較情報を捨て去ってしまうという問題点に対処することです。

KMPは、不一致時に text のポインタを戻さず、pattern のポインタを適切にジャンプさせることでこれを実現します。この「適切なジャンプ」は、パターン自身が持つ「接頭辞がそのまま接尾辞になっている部分」の情報、つまり LPS 配列によって導かれます。LPS 配列はパターンに対して一度だけ線形時間で計算され、その後の検索プロセスで効率的なシフト量を決定するために利用されます。

KMPアルゴリズムは、
– LPS配列の計算 (O(M))
– KMP検索本体 (O(N))
という二つの主要なフェーズから構成され、全体の時間計算量は O(N+M)、空間計算量は O(M) となります。この性能は、多くの実用的なパターンマッチングの場面で十分高速であり、特にテキストを一方通行で読み込む必要があるストリーム処理において大きな利点を発揮します。

KMP アルゴリズムの学習は、単に特定の文字列検索手法を知ること以上の意味を持ちます。それは、問題の根本原因（素朴なアルゴリズムの無駄）を深く理解し、それまでの計算で得られた情報をいかに効率的に再利用するかというアルゴリズム設計の哲学を学ぶ機会となります。LPS 配列のような補助的なデータ構造を導入し、状態遷移（一致、不一致、ジャンプ）を巧みに設計することで、非効率な処理を線形時間処理へと劇的に改善できることを KMP アルゴリズムは鮮やかに示しています。

現代では、さらに改良された様々な文字列検索アルゴリズムが存在しますが、KMPアルゴリズムが提示した「失敗時の情報の活用」というブレークスルーは、その後のアルゴリズム研究に大きな影響を与えました。KMPを理解することは、文字列処理だけでなく、より広範なアルゴリズム設計における重要な知見を得ることに繋がります。

本記事を通して、KMPアルゴリズムの仕組み、LPS配列の役割と計算、そしてその効率性の源泉について深く理解していただけたなら幸いです。この強力なアルゴリズムは、私たちのデジタル生活の基盤を支える多くの場面で活躍しています。