KMP法（KMPアルゴリズム）とは？効率的な文字列探索アルゴリズムの基本

By /

はい、承知いたしました。KMP法（KMPアルゴリズム）について、約5000語の詳細な解説記事を作成します。

KMP法とは？ 効率的な文字列探索アルゴリズムの基本

1. はじめに：文字列探索の重要性と効率化の課題

コンピュータサイエンスの世界では、文字列を扱う機会は非常に多く、その中でも「ある文字列（パターン）が別のより長い文字列（テキスト）の中に含まれているか、含まれているとすればどの位置か」を探す「文字列探索（String Searching）」あるいは「パターンマッチング（Pattern Matching）」は、最も基本的かつ頻繁に行われる操作の一つです。

テキストエディタでの単語検索、インターネット検索エンジン、生物学におけるDNAやRNA配列の解析、ネットワークセキュリティにおけるパケット検査、コンパイラでの字句解析など、その応用範囲は広大です。これらの処理においては、対象となるテキストやパターンが非常に長くなることが少なくありません。例えば、ゲノム配列は数十億塩基対にも及び、インターネット上の文書も膨大です。このような状況で非効率な探索を行えば、処理に膨大な時間がかかってしまい、実用になりません。したがって、文字列探索をいかに高速に行うかという問題は、古くから重要な研究課題でした。

文字列探索アルゴリズムの中で、最も直感的で理解しやすいのは「単純な文字列探索アルゴリズム（Naive String Searching Algorithm）」、別名「力まかせ探索（Brute-Force Search）」と呼ばれる手法です。しかし、この単純な手法には、特定の条件下で計算時間が非常に長くなるという大きな欠点があります。

この計算時間の問題を劇的に改善した画期的なアルゴリズムが、「KMP法」です。KMP法は、その考案者であるDonald Knuth、Vaughan Pratt、およびJames Morrisの頭文字をとって名付けられました。彼らがこのアルゴリズムを論文として発表したのは1977年ですが、PrattとMorrisはこれより数年前に独立して同じアイデアに到達していました。

KMP法は、テキストの各文字を最大でも1度しか比較しないという驚くべき特性を持ち、理論上可能な最速の文字列探索アルゴリズムの一つである線形時間アルゴリズム（O(n+m)の時間計算量、ここでnはテキスト長、mはパターン長）を実現しています。これは、単純な文字列探索アルゴリズムの最悪時間計算量O(nm)と比較して、特に長いテキストやパターンにおいて圧倒的に高速であることを意味します。

本記事では、このKMP法がどのようにして効率的な探索を実現しているのか、その仕組みを詳細に解説します。具体的には、まず単純な文字列探索アルゴリズムの限界を示し、次にKMP法の核心である「失脚関数（Failure Function）」または「境界配列（Border Array）」と呼ばれる前処理について、その概念と計算方法を詳しく説明します。最後に、この前処理を用いてどのように高速な探索を行うのか、アルゴリズム全体をステップバイステップで解説します。

2. 単純な文字列探索アルゴリズムとその限界

KMP法の優位性を理解するためには、まず単純な文字列探索アルゴリズムの動作とその非効率性を把握することが重要です。

単純な文字列探索アルゴリズムは、以下のように動作します。

  1. テキストの先頭からパターンを合わせるように配置します。
  2. パターンの各文字と、それに対応するテキストの文字を左から順に比較します。
  3. パターンの全ての文字がテキストの文字と一致すれば、パターンが見つかったことになります。その位置（テキストの何番目からパターンが始まっているか）を報告します。
  4. もし途中で一致しない文字が見つかった場合、パターンをテキスト中で1文字分だけ右にずらします。
  5. パターンが見つかるか、パターンをテキストの最後までずらしても見つからなくなるまで、2～4のステップを繰り返します。

例を見てみましょう。
テキスト T = “ABABABABAC”
パターン P = “ABABC“

  • 最初にパターンをテキストの先頭に合わせます。
    T: A B A B A B A B A C
    P: A B A B C
    ^
    テキストとパターンを比較します。T[0]とP[0]は一致(A)。T[1]とP[1]は一致(B)。T[2]とP[2]は一致(A)。T[3]とP[3]は一致(B)。T[4]とP[4]を比較すると、T[4]は’A’、P[4]は’C’で一致しません。ここで不一致が発生しました。

  • 単純なアルゴリズムでは、パターンをテキスト中で1文字分右にずらします。
    T: A B A B A B A B A C
    P: A B A B C
    ^
    再度比較します。T[1]とP[0]を比較します… これも一致しません。

  • さらにパターンを1文字分右にずらします。
    T: A B A B A B A B A C
    P: A B A B C
    ^
    比較します。T[2]とP[0]は一致(A)。T[3]とP[1]は一致(B)。T[4]とP[2]は一致(A)。T[5]とP[3]は一致(B)。T[6]とP[4]を比較すると、T[6]は’A’、P[4]は’C’で一致しません。不一致です。

  • パターンを1文字分右にずらします。
    T: A B A B A B A B A C
    P: A B A B C
    ^
    比較します。T[3]とP[0]は一致(A)。T[4]とP[1]は一致(B)。T[5]とP[2]は一致(A)。T[6]とP[3]は一致(B)。T[7]とP[4]を比較すると、T[7]は’B’、P[4]は’C’で一致しません。不一致です。

  • さらにパターンを1文字分右にずらします。
    T: A B A B A B A B A C
    P: A B A B C
    ^
    比較します。T[4]とP[0]は一致(A)… 以降一致が続き、T[8]とP[4]を比較します。T[8]は’A’、P[4]は’C’で一致しません。不一致です。

このように、単純な文字列探索では、不一致が発生するたびにパターンをたった1文字分だけずらし、再度先頭から比較をやり直します。

計算量の問題点:

この「1文字ずらして最初からやり直し」という処理は、特定のケースで非常に非効率になります。最も典型的な worst-case は、テキストが同じ文字の繰り返しで、パターンがその文字の繰り返しに最後に別の文字を付け加えた形になっている場合です。

例:
テキスト T = “AAAAAAAAAAAAAAA” (Aがn個)
パターン P = “AAAAAB” (Aがm-1個、最後にB)

  1. パターンを先頭に合わせます。P[0]からP[m-2]まではテキストと一致しますが、P[m-1](‘B’)はT[m-1](‘A’)と一致しません。不一致です。比較回数はm回。
  2. パターンを1文字ずらします。P[0]からP[m-2]まではテキストと一致しますが、P[m-1]とテキストの対応文字は一致しません。不一致です。比較回数はm回。
  3. これをパターンがテキストの最後まで到達するまで繰り返します。パターンを配置できる位置は n-m+1 箇所あります。各位置で最悪m回の比較が行われます。

したがって、最悪の場合の比較回数は約 (n-m+1) * m 回となります。これは O(nm) の時間計算量です。テキスト長nが100万、パターン長mが1000だった場合、比較回数は約 10^6 * 10^3 = 10^9 回となり、かなりの時間を要します。

この非効率性の根本原因は、不一致が起きたときに、それまでの比較で得られた情報を全く利用していないことです。単純なアルゴリズムは、不一致が起きると「どうせ1文字ずらしてもまた最初から比較するんだから、これまでのことは忘れよう」という態度をとります。KMP法は、この点を改善することで効率化を実現します。

3. KMP法の核心：ずらし方を賢く決める

KMP法が単純な文字列探索アルゴリズムより高速なのは、不一致が発生した際に、パターンをどれだけずらせば効率的かを、パターン自身の構造に基づいて事前に計算しておき、その情報を使ってずらし方を決定するからです。これにより、テキストの同じ文字を何度も比較し直すという無駄を省き、テキストポインタを後戻りさせない（常にテキストを前に読み進める）ようにします。

鍵となるアイデアは以下の通りです。

テキスト T の i 番目の文字と、パターン P の j 番目の文字 P[j] で不一致が発生したとします (T[i] != P[j])。このとき、直前まで (P[0] から P[j-1] まで) はテキストとパターンが一致していたはずです。つまり、T[i-j ... i-1] は P[0 ... j-1] と完全に一致しています。

T: ... T[i-j] ... T[i-1] T[i] ...
P: P[0] ... P[j-1] P[j] ...
(ここで不一致)

不一致が起きた T[i] は既に見た文字です。パターンをずらして、次の比較を T[i] に対して行うべきですが、パターンをどの位置にずらせばよいでしょうか？

単純なアルゴリズムのように1文字だけずらすのは非効率です。例えば、パターンが “ABAB” でテキストが “ABABA” のときに、最後の’B’で不一致が起きたとします。
T: A B A B A
P: A B A B
^ (不一致 T[4] != P[4] - 実際はP[4]は存在しないので P[3] = B と T[4] = A が不一致)
ここで j は 4 (0オリジンでパターン長m=4)。P[0...3] が T[0...3] と一致しています。単純なアルゴリズムではパターンを1文字ずらしますが、
T: A B A B A
P: A B A B
^
これではすぐに P[0] と T[1] (‘B’と’B’) が一致しないことが分かります。

賢いずらし方とは、現在一致しているパターンの接頭辞 P[0...j-1] の中で、「それ自身の真の接頭辞（proper prefix）であり、かつ真の接尾辞（proper suffix）でもある」最長の文字列を見つけ、その文字列がテキストの T[i-j ... i-1] のどこに一致していたかを利用して、パターンをその位置にずらす**ことです。

「真の接頭辞」とは、文字列自身を含まない接頭辞のことです（例: “ABAB” の真の接頭辞は “”, “A”, “AB”, “ABA”）。
「真の接尾辞」とは、文字列自身を含まない接尾辞のことです（例: “ABAB” の真の接尾辞は “”, “B”, “AB”, “BAB”）。

例: パターン P = “ABABC” で、j=4 (P[3] の文字 ‘B’ まで一致していて、T[i] と P[4] の ‘C’ で不一致が起きた場合)。
一致していたのは P[0...3] = “ABAB” です。
“ABAB” の真の接頭辞: “”, “A”, “AB”, “ABA”
“ABAB” の真の接尾辞: “”, “B”, “AB”, “BAB”
これらの中で、接頭辞でも接尾辞でもあるものは “”, “AB” です。最も長いのは “AB” (長さ2) です。

これは何を意味するのでしょうか？ P[0...3] が T[i-4 ... i-1] と一致しているということは、T[i-4 ... i-1] も “ABAB” であるということです。そして “ABAB” の最長の共通する真の接頭辞/接尾辞は “AB” ですから、T[i-4 ... i-3] は “AB” であり、T[i-2 ... i-1] も “AB” であることが確定します。

T: ... A B A B A ... (ここが T[i-4 ... i-1])
P: A B A B C ... (ここで不一致 T[i] と P[4])
^---^ (P[0...1] = "AB")
^---^ (P[2...3] = "AB")

つまり、テキストの T[i-2 ... i-1] の部分が “AB” であることが分かっています。この “AB” はパターンの P[0...1] と同じです。したがって、パターンを P[0] が T[i-2] に合うようにずらせば、テキストの T[i-2 ... i-1] の部分とパターンの P[0 ... 1] が一致した状態から探索を再開できます。

T: ... A B A B A ...
P: A B A B C ...
^ (ずらした後のP[0])
この場合、ずらした後のパターンの先頭は T[i-2] に位置し、パターンの新しい比較位置は P[2] になります。元々 P[4] で不一致だったので、新しい比較は T[i] と P[2] で行われます。

重要なのは、このずらし方によって、テキストの T[i-2] より前の部分や、ずらした後のパターンで既に一致が確定している部分 (P[0...1] と T[i-2...i-1]) を再度比較する必要がないということです。テキストポインタ i はそのまま T[i] を指したままで、パターンポインタ j だけが lps[j-1] の値（今回の例では “ABAB” の lps 値が 2 なので j=2）に移動すればよいのです。

4. 失脚関数（Failure Function）または境界配列（Border Array）の計算

上記の賢いずらし方を実現するために、KMP法はパターンに対して事前の計算を行います。この計算結果は「失脚関数 (Failure Function)」や「境界配列 (Border Array)」などと呼ばれ、多くの場合 next 配列や lps (longest proper prefix which is also suffix) 配列として実装されます。

ここでは lps 配列と呼びます。lps[j] は、パターンの P[0...j] という文字列において、真の接頭辞であり、かつ真の接尾辞でもある最長の文字列の長さを格納します。

例: パターン P = “ABABCABAB” (m=9)

j P[j] P[0…j] 真の接頭辞/真の接尾辞の共通部分のリスト 最長の長さ lps[j]
0 A “A” なし (真の接頭辞/接尾辞が存在しない) 0 0
1 B “AB” “” 0 0
2 A “ABA” “A” 1 1
3 B “ABAB” “”, “AB” 2 2
4 C “ABABC” “” 0 0
5 A “ABabca” “A” 1 1
6 B “ABABCAb” “”, “AB” 2 2
7 A “ABABCABa” “A”, “ABA” 3 3
8 B “ABABCABAb” “”, “AB”, “ABAB” 4 4

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

さて、この lps 配列は、文字列探索アルゴリズムのどこで使うのでしょうか？ 先ほどの不一致の例を思い出してください。テキストの T[i] とパターンの P[j] で不一致が発生しました。このとき、P[0...j-1] はテキストの対応する部分と一致しています。私たちは、パターンの P[0...j-1] という文字列の中で、最長の真の接頭辞かつ真の接尾辞の長さ (lps[j-1]) を知りたいのです。

もし lps[j-1] = k であれば、それは P[0...k-1] と P[j-k...j-1] が一致していることを意味します。そして、P[j-k...j-1] はテキストの T[i-k...i-1] と一致しています（なぜなら T[i-j...i-1] が P[0...j-1] と一致しているからです）。
したがって、テキストの T[i-k...i-1] の部分は P[0...k-1] と一致していることが分かります。私たちは、パターンを P[0] が T[i-k] に来るようにずらしたいのですが、テキストの T[i-k...i-1] とパターンの P[0...k-1] は既に一致が確認できているので、この部分の再比較は不要です。テキストポインタ i はそのままに、パターンポインタ j を k に移動させれば、次の比較は T[i] と P[k] で行えばよいのです。

つまり、T[i] と P[j] で不一致が発生した場合、パターンポインタ j を lps[j-1] に更新することで、テキストポインタ i を後戻りさせることなく、次の有効な比較位置にパターンをずらすことができます。

ただし、j=0 のときに不一致が発生した場合はどうでしょうか？ これはパターンの最初の文字 P[0] がテキストの T[i] と一致しないことを意味します。この場合、パターンをずらしても P[0] が T[i] と一致する可能性はありません。したがって、テキストポインタ i を1つ進めて、次の文字 T[i+1] からパターンの先頭 P[0] と比較を始めるしかありません。このとき、パターンポインタ j は 0 のままです。

この lps 配列は、パターンの長さ m に応じて計算されます。この計算自体も効率的に行う必要があります。lps 配列を計算するためのアルゴリズムも、KMP法の一部と考えることができます。この計算アルゴリズムも、KMPの探索部分と似た線形時間で行えます。

lps配列の計算アルゴリズムの詳細

lps 配列 lps[0...m-1] を計算します。ここで lps[i] はパターン P[0...i] の最長の真の接頭辞かつ真の接尾辞の長さを格納します。

  1. lps[0] は常に 0 です。パターンの最初の文字 P[0] だけで構成される文字列には、真の接頭辞も真の接尾辞も存在しないためです。
  2. lps 配列の i=1 から m-1 までの値を、既に計算済みの値を利用して効率的に計算します。
  3. 計算には2つのポインタを使います。
    • length：現在調べている真の接頭辞兼接尾辞の長さ（次に一致すると期待される文字のインデックス）
    • i：現在 lps の値を計算しているパターンのインデックス

初期状態:
lps[0] = 0
length = 0 (これは P[0...0] の lps 値の後の状態、つまり次に期待される長さ)
i = 1 (これから lps[1] を計算する)

ループ: i を 1 から m-1 まで繰り返します。

各ステップ i で、P[i] と P[length] を比較します。

  • Case 1: P[i] と P[length] が一致する場合
    これは、長さ length の共通部分に P[i] (接尾辞側の次の文字) と P[length] (接頭辞側の次の文字) が付け加えられて、より長い共通部分ができたことを意味します。
    パターン: ... P[length-1] P[length] ... P[i-1] P[i] ...
    <-- length --> <-- length -->
    P[0...length-1] は P[i-length...i-1] と一致しています。P[length] と P[i] が一致すれば、P[0...length] は P[i-length...i] と一致することになります。
    新しい共通部分の長さは length + 1 です。
    lps[i] = length + 1 と設定し、次のステップのために length を length + 1 に更新します。i は次の文字に進みます。

  • Case 2: P[i] と P[length] が一致しない場合
    現在の length で示される共通部分（P[0...length-1]）の次に P[i] を付けると一致しないということです。より短い共通部分を探す必要があります。
    次に短い共通部分の長さは、現在の共通部分 P[0...length-1] の lps 値、つまり lps[length-1] が教えてくれます。
    length を lps[length-1] に更新します。
    そして、新しい length の値を使って、再度 P[i] と P[length] を比較します（これは while ループで行います）。

    ただし、length が既に 0 の場合（これ以上短い共通部分がない）、そして P[i] が P[0] とも一致しない場合は、lps[i] は 0 となります。もし length が 0 だが P[i] と P[0] が一致する場合は、共通部分の長さが 1 になるので lps[i] = 1 とし、length を 1 に更新します。この length=0 の特別なケースは、上記の Case 1 & 2 のロジックで自然に処理できます。

    より正確な Case 2 の処理：
    length が 0 より大きい場合: length を lps[length-1] に更新し、再度 P[i] と P[length] を比較するためのループを続行します。
    length が 0 の場合: P[i] は P[0] と比較されます。
    * もし P[i] と P[0] が一致すれば、新しい共通部分の長さは 1 です。lps[i] = 1 とし、length を 1 に更新します。
    * もし P[i] と P[0] が一致しなければ、共通部分は存在しないので lps[i] = 0 とし、length は 0 のままです。

この Case 2 のロジックは、while ループとそれに続く if でより簡潔に書けます。

“`python

Python風擬似コードでの lps 配列計算

def computeLPSArray(pattern):
m = len(pattern)
lps = [0] * m # サイズmの配列を0で初期化

length = 0 # lps[i-1] の値 (前の文字までの共通部分の長さ)
i = 1 # 現在 lps[i] を計算しているインデックス

# lps[0] は既に 0 で初期化されている

while i < m:
    if pattern[i] == pattern[length]:
        # Case 1: 一致した場合
        length += 1
        lps[i] = length
        i += 1
    else:
        # Case 2: 不一致の場合
        if length != 0:
            # length > 0 の場合、lps[length-1] に戻ってより短い共通部分を探す
            # ここで注意: i はそのまま、pattern[i] は移動した pattern[length] と再比較される
            length = lps[length - 1]
        else:
            # length == 0 の場合、P[i] != P[0] ということ。
            # 共通部分は 0
            lps[i] = 0
            i += 1 # i だけ進めて次の文字を調べる

“`

このアルゴリズムをステップバイステップで追ってみましょう。パターン P = “ABABCABAB” (m=9)

  • lps = [0, 0, 0, 0, 0, 0, 0, 0, 0]
  • length = 0, i = 1
ステップ i length P[i] P[length] 比較 動作 lps[i] 設定 lps配列の状態
初期 1 0 – – – – – [0,0,0,0,0,0,0,0,0]
i=1 1 0 B A B!=A length=0 なので lps[1]=0, i++ 0 [0,0,0,0,0,0,0,0,0]
i=2 2 0 A A A==A length++ (1), lps[2]=1, i++ 1 [0,0,1,0,0,0,0,0,0]
i=3 3 1 B B B==B length++ (2), lps[3]=2, i++ 2 [0,0,1,2,0,0,0,0,0]
i=4 4 2 C A C!=A length=2 != 0 なので length = lps[2] = 1 – [0,0,1,2,0,0,0,0,0]
再比較 4 1 C B C!=B length=1 != 0 なので length = lps[1] = 0 – [0,0,1,2,0,0,0,0,0]
再比較 4 0 C A C!=A length=0 なので lps[4]=0, i++ 0 [0,0,1,2,0,0,0,0,0]
i=5 5 0 A A A==A length++ (1), lps[5]=1, i++ 1 [0,0,1,2,0,1,0,0,0]
i=6 6 1 B B B==B length++ (2), lps[6]=2, i++ 2 [0,0,1,2,0,1,2,0,0]
i=7 7 2 A A A==A length++ (3), lps[7]=3, i++ 3 [0,0,1,2,0,1,2,3,0]
i=8 8 3 B B B==B length++ (4), lps[8]=4, i++ 4 [0,0,1,2,0,1,2,3,4]
ループ終了 9 4 – – – i >= m となったため終了 – [0,0,1,2,0,1,2,3,4]

計算結果の lps 配列 [0, 0, 1, 2, 0, 1, 2, 3, 4] は、手計算で確認した結果と一致します。

この lps 配列の計算にかかる時間計算量は O(m) です。なぜなら、i ポインタは常に前進し、最大で m-1 ステップ進むからです。length ポインタは一致した場合はインクリメントされ、不一致の場合はデクリメントされますが、length がインクリメントされる回数は i が進む回数（最大m回）を超えることはなく、length がデクリメントされる回数も length がインクリメントされた回数を超えることはありません。したがって、全体の操作回数は O(m) となります。

5. KMP文字列探索アルゴリズムの詳細

lps 配列が計算できたら、いよいよこれを使って効率的な文字列探索を行います。KMPの探索アルゴリズムも2つのポインタを使います。

  • i：テキスト T の現在比較している文字のインデックス
  • j：パターン P の現在比較している文字のインデックス

初期状態:
i = 0 (テキストの先頭)
j = 0 (パターンの先頭)

探索は、i がテキストの最後まで (i < n) に到達するまで続けます。

各ステップで T[i] と P[j] を比較します。

  • Case 1: T[i] と P[j] が一致する場合
    これは、現在の位置で一致が続いていることを意味します。両方のポインタを1つ進めて、次の文字の比較に移ります。
    i++
    j++

    もし j がパターンの長さに達した場合 (j == m)、パターンがテキスト中に見つかったことを意味します。現在の i の位置からパターンの長さ分戻った位置 (i - m) がパターンが見つかった開始位置です。発見を報告します。

    パターンが見つかった後、次の出現を探すために探索を続行する必要があります。単純なアルゴリズムのように i を i-m+1 に戻し、j を 0 にリセットするのは非効率です。パターンの最後の m-1 文字がテキストと一致していることは分かっています。この一致している部分の「最長の真の接頭辞かつ真の接尾辞」の情報 (lps[m-1]) を利用して、パターンを賢くずらします。
    パターンポインタ j を lps[m-1] に更新します。テキストポインタ i はそのままです。これにより、テキストの最後に見つかったパターンの一部とパターンの新しい先頭部分が重なるようにパターンが配置され、その重なり部分は再比較不要となります。次の比較は T[i] と P[lps[m-1]] で行われます。

  • Case 2: T[i] と P[j] が一致しない場合
    ここで lps 配列が登場します。
    もし j > 0 の場合（つまり、パターンの途中で不一致が起きた場合）、これは P[0...j-1] がテキストの T[i-j...i-1] と一致していることを意味します。パターンの新しい位置は、この一致している P[0...j-1] の「最長の真の接頭辞かつ真の接尾辞」の長さ lps[j-1] によって決まります。
    パターンポインタ j を lps[j-1] に更新します。テキストポインタ i はそのままです。次の比較は T[i] と新しい P[j] で行われます。

    もし j == 0 の場合（つまり、パターンの最初の文字 P[0] がテキストの T[i] と一致しない場合）、パターンをずらしても現在の T[i] と P[0] が一致する可能性はありません。したがって、テキストポインタ i を1つ進めて、テキストの次の文字 T[i+1] とパターンの先頭 P[0] の比較を試みます。パターンポインタ j は 0 のままです。
    i++
    j は 0 のまま。

探索は、i がテキストの長さに達するか、あるいは全ての可能性を調べ尽くすまで続きます。テキストの最後まで行ってもパターンが見つからなければ、見つからなかったと報告します。

“`python

Python風擬似コードでの KMP 探索

def KMPSearch(text, pattern):
n = len(text)
m = len(pattern)

if m == 0: # エッジケース: パターンが空文字列
    print("Pattern found at index 0 (empty pattern matches anywhere)")
    return

if n == 0: # エッジケース: テキストが空文字列
    print("Text is empty, pattern not found")
    return

if m > n: # エッジケース: パターンがテキストより長い
    print("Pattern is longer than text, pattern not found")
    return

# lps配列を事前に計算
lps = computeLPSArray(pattern) # computeLPSArray関数は前節で定義したものとする

i = 0 # text[] のポインタ
j = 0 # pattern[] のポインタ (lps[] のインデックスでもある)

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

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

        if j == m:
            # パターン全体が一致した
            # マッチ開始位置は i - m
            found_indices.append(i - m)

            # 次の出現を探すために pattern をずらす
            # j を lps[j-1] (つまり lps[m-1]) に更新
            # テキストポインタ i はそのまま
            j = lps[j - 1] # あるいは lps[m-1]

    else:
        # Case 2: 文字が不一致
        if j != 0:
            # pattern の途中で不一致
            # lpsテーブルに従って pattern ポインタを戻す
            # text ポインタ i はそのまま
            j = lps[j - 1]
        else:
            # pattern の先頭で不一致 (j == 0)
            # text ポインタを一つ進める
            # pattern ポインタ j は 0 のまま
            i += 1

if found_indices:
    print(f"Pattern found at indices: {found_indices}")
else:
    print("Pattern not found in text")

“`

KMP探索のステップバイステップ例

テキスト T = “ABABDABACDABABCABAB” (n=19)
パターン P = “ABABCABAB” (m=9)
lps 配列 = [0, 0, 1, 2, 0, 1, 2, 3, 4]

初期状態: i = 0, j = 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
^
T[0](‘A’) == P[0](‘A’) -> 一致。i=1, j=1。

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
^
T[1](‘B’) == P[1](‘B’) -> 一致。i=2, j=2。

… (一致が続く) …

T[7](‘A’) == P[7](‘A’) -> 一致。i=8, j=8。
現在: i=8, j=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
^
T[8](‘C’) と P[8](‘B’) -> 不一致。

j は 8 で 0 より大きい。j = lps[j-1]、つまり j = lps[8-1] = lps[7] = 3 に更新。i は 8 のまま。
新しい j は 3 なので、次の比較は T[8](‘C’) と P[3](‘B’) で行われます。

T: A B A B D A B A C D A B A B C A B A B
^ (i=8)
P: A B C A B A B
^ (新しいj=3)
T[8](‘C’) と P[3](‘B’) -> 不一致。

j は 3 で 0 より大きい。j = lps[j-1]、つまり j = lps[3-1] = lps[2] = 1 に更新。i は 8 のまま。
新しい j は 1 なので、次の比較は T[8](‘C’) と P[1](‘B’) で行われます。

T: A B A B D A B A C D A B A B C A B A B
^ (i=8)
P: B C A B A B
^ (新しいj=1)
T[8](‘C’) と P[1](‘B’) -> 不一致。

j は 1 で 0 より大きい。j = lps[j-1]、つまり j = lps[1-1] = lps[0] = 0 に更新。i は 8 のまま。
新しい j は 0 なので、次の比較は T[8](‘C’) と P[0](‘A’) で行われます。

T: A B A B D A B A C D A B A B C A B A B
^ (i=8)
P: A B A B C A B A B
^ (新しいj=0)
T[8](‘C’) と P[0](‘A’) -> 不一致。

j は 0 です。i を1つ進めて、j は 0 のまま。i=9, j=0。
次の比較は T[9](‘D’) と P[0](‘A’) です。

T: A B A B D A B A C D A B A B C A B A B
^ (i=9)
P: A B A B C A B A B
^ (j=0)
T[9](‘D’) と P[0](‘A’) -> 不一致。

j は 0 です。i を1つ進めて、j は 0 のまま。i=10, j=0。
次の比較は T[10](‘A’) と P[0](‘A’) です。

T: A B A B D A B A C D A B A B C A B A B
^ (i=10)
P: A B A B C A B A B
^ (j=0)
T[10](‘A’) == P[0](‘A’) -> 一致。i=11, j=1。

… (一致が続く) …

T[18](‘B’) == P[8](‘B’) -> 一致。i=19, j=9。
現在: i=19, j=9

T: A B A B D A B A C D A B A B C A B A B
^ (i=19)
P: A B A B C A B A B
^ (j=9)
j が 9 になりました。これはパターンの長さ m (9) と等しいので、パターンがテキスト中で見つかりました。
見つかった位置は i - m = 19 - 9 = 10 です。
発見を報告します。インデックス 10 からパターンが見つかりました。

次に探すために、j = lps[j-1] = lps[9-1] = lps[8] = 4 に更新します。i は 19 のまま。
新しい j は 4 です。

T: A B A B D A B A C D A B A B C A B A B
^ (i=19)
P: C A B A B
^ (新しいj=4)
これで i=19 となりましたが、テキストの長さ n も 19 なので、i < n の条件 (19 < 19) が偽となり、ループが終了します。テキストの最後まで探索が終わりました。

見つかった位置はインデックス 10 です。
この例では1箇所だけでしたが、もしテキストがもっと長ければ、j = lps[m-1] への更新により、重なった部分の再比較なしに次の可能性から効率的に探索を続けることができます。

例えば、テキストが “ABABCABAB” で、パターンが “ABAB” (m=4, lps=[0,0,1,2]) の場合を考えます。
T: A B A B C A B A B (n=9)
P: A B A B (m=4)
lps: [0,0,1,2]

  1. i=0, j=0. T[0…3] == P[0…3]. 一致. i=4, j=4.
  2. j==m (4==4). マッチ発見 at i-m = 4-4 = 0. 報告: 0。
  3. 次を探すため j = lps[m-1] = lps[3] = 2. i は 4 のまま。
    現在 i=4, j=2. 比較は T[4](‘C’) と P[2](‘A’).
    T: A B A B C A B A B
    ^ (i=4)
    P: A B
    ^ (j=2)
  4. T[4](‘C’) != P[2](‘A’). 不一致. j != 0. j = lps[j-1] = lps[2-1] = lps[1] = 0. i は 4 のまま。
    現在 i=4, j=0. 比較は T[4](‘C’) と P[0](‘A’).
    T: A B A B C A B A B
    ^ (i=4)
    P: A B A B
    ^ (j=0)
  5. T[4](‘C’) != P[0](‘A’). 不一致. j == 0. i++ (5), j は 0 のまま。
    現在 i=5, j=0. 比較は T[5](‘A’) と P[0](‘A’).
    T: A B A B C A B A B
    ^ (i=5)
    P: A B A B
    ^ (j=0)
  6. T[5](‘A’) == P[0](‘A’). 一致. i=6, j=1.
    … 一致が続く …
    T[8](‘B’) == P[3](‘B’). 一致. i=9, j=4.
    現在 i=9, j=4.
    T: A B A B C A B A B
    ^ (i=9)
    P: A B
    ^ (j=4) - この位置の文字は存在しない (m=4)
  7. j==m (4==4). マッチ発見 at i-m = 9-4 = 5. 報告: 5。
  8. 次を探すため j = lps[m-1] = lps[3] = 2. i は 9 のまま。
    現在 i=9, j=2.
    T: A B A B C A B A B
    ^ (i=9)
    P: A B
    ^ (j=2)
  9. i < n (9 < 9) が偽となりループ終了。

結果: パターンはインデックス 0 と 5 で見つかりました。
この例では、パターンが完全に見つかった後 (j == m) に j = lps[m-1] とすることで、テキストポインタ i を戻すことなく効率的に次の探索を開始できたことが分かります。

6. 計算量と空間計算量

KMP法の効率性を改めて評価しましょう。

時間計算量:
KMP法は大きく分けて2つのフェーズからなります。
1. lps 配列の計算：パターンの長さ m に対して O(m) の時間で計算できます。
2. 文字列探索フェーズ：テキスト長 n とパターン長 m に対して O(n) の時間で実行できます。

なぜ探索フェーズが O(n) になるのでしょうか？
* テキストポインタ i はループ全体を通じて単調増加し、最大で n ステップ進みます。
* パターンポインタ j は、一致した場合はインクリメントされ、不一致の場合は lps[j-1] に基づいてデクリメントされます。
* j がインクリメントされるのは、T[i] == P[j] の場合か、j == 0 で不一致かつ i がインクリメントされる場合（後者は i の移動でカウント）です。j が 0 から m-1 までインクリメントされる合計回数は、パターンが見つかった回数を含めても n を超えることはありません。なぜなら、j が m になるとマッチが見つかり、j は lps[m-1] に戻るため、合計のインクリメント回数はテキストをスキャンする回数に比例するからです。
* j がデクリメントされる（j = lps[j-1]）回数は、その直前の j の値が 1以上であった回数以下です。j がインクリメントされた回数の合計が O(n) であるため、j がデクリメントされる回数も O(n) を超えません。

したがって、i の移動と j の移動（インクリメント/デクリメント）の総回数は、合わせて O(n + m) のオーダーになります。パターンマッチの発見処理や lps 計算はそれぞれ O(m) または O(1) ですので、探索フェーズ全体は O(n) と考えることができます（より厳密には O(n+m) ですが、m << n の場合は O(n) に漸近します）。

KMP法全体の時間計算量は、lps 計算 (O(m)) と探索 (O(n)) の合計である O(n + m) となります。これは、テキストとパターンをそれぞれ1回ずつ読むだけで探索が完了することにほぼ相当し、理論上の限界に近い効率性です。

比較対象である単純な文字列探索アルゴリズムの最悪時間計算量 O(nm) と比べると、その差は歴然です。特に nやmが大きい場合にKMP法の優位性が発揮されます。

空間計算量:
KMP法は、lps 配列を格納するためにパターンの長さ m に比例する追加メモリが必要です。テキストやパターン自体を格納する空間を除くと、KMP法に必要な空間計算量は O(m) です。
単純な文字列探索アルゴリズムは、通常、追加の空間はほとんど不要（O(1)）であるため、空間計算量に関しては単純なアルゴリズムの方が優れています。しかし、現代のコンピュータのメモリ容量を考慮すると、O(m) の追加空間は、多くの場合、時間効率の劇的な向上に見合う十分小さなコストと言えます。

7. KMP法の利点と欠点

KMP法の利点：

  • 高い効率性: 最悪の場合でも線形時間 O(n+m) で動作します。テキストポインタを後戻りさせないため、テキストの各文字を最大でも1度しか比較しません（ただし、パターンポインタは後戻りします）。
  • 保証された性能: 単純なアルゴリズムのような特定の入力に対する性能劣化がありません。常に効率的に動作します。
  • 理論的なエレガンス: パターンの自己構造を利用して探索を効率化するという美しいアイデアに基づいています。

KMP法の欠点：

  • アルゴリズムの複雑さ: 単純なアルゴリズムに比べて、lps 配列の概念と計算、およびそれを使った探索ロジックの理解と実装がやや複雑です。
  • 追加の空間: lps 配列のためにパターンの長さ分の追加メモリが必要です (O(m))。

8. KMP法の応用例

KMP法は、その効率性から様々な分野で活用されています。

  • テキストエディタとユーティリティ: ファイル内の文字列検索 (grepなど) や置換機能のバックエンドとして使用されることがあります。
  • バイオインフォマティクス: DNAやRNAなどの巨大な配列データの中から特定の短い配列（パターン）を検索する際に、KMP法の応用や類似のアルゴリズムが使用されます。
  • ネットワークセキュリティ: 侵入検知システム (IDS) などで、ネットワークパケットのペイロードの中から悪意のあるパターンのシグネチャを高速に検索するために利用されます。
  • コンパイラとインタプリタ: ソースコードの字句解析（トークン分割）において、特定のキーワードや識別子パターンを効率的に見つけるために、パターンマッチング技術が用いられます。
  • データ圧縮: 特定の繰り返しパターンを効率的に検出する際に、KMP法のような線形時間のパターンマッチング手法のアイデアが役立つことがあります。

9. KMP法の実装における注意点

KMP法を実際に実装する際には、いくつかの点に注意が必要です。

  • 0-based vs 1-basedインデックス: 配列のインデックスを0から始めるか1から始めるかで、アルゴリズムの記述や lps 配列の定義に微妙な違いが生じます。本記事では0-basedインデックスを使用しました。lps[j] は P[0...j] の接頭辞/接尾辞長として定義しましたが、文献によっては lps[j] を P[0...j-1] の情報として定義する場合もあります。この場合、配列サイズやインデックスの扱いに注意が必要です。特に不一致時の j = lps[j-1] という遷移は、不一致が P[j] で起きた（つまり P[0...j-1] は一致していた）状況を反映しています。
  • lps[0] の定義: lps[0] の値を 0 とする（P[0...0] の共通部分長）場合と、KMPの探索部分の便宜のために -1 とする場合があります。-1 とすることで、探索ループで j == 0 の場合と j > 0 の場合を少し統一的に書ける場合があります（j = lps[j] と遷移するコードを書く場合など）。本記事の擬似コードでは、lps 配列計算では lps[0]=0 とし、探索では j=0 のケースを分けて記述しています。これは理解しやすい方法の一つです。
  • 空文字列や長さの比較: パターンが空文字列の場合、テキストが空文字列の場合、パターンがテキストより長い場合といったエッジケースの処理を忘れないことが重要です。

10. 他の文字列探索アルゴリズムとの関係

KMP法以外にも、様々な文字列探索アルゴリズムが存在します。

  • Boyer-Moore法: KMP法と同様に非常に効率的なアルゴリズムで、多くの場合KMP法よりも高速に動作します。Boyer-Moore法は、パターンをテキストの右側から比較を始め、不一致が起きた文字やパターン内の文字の位置に基づいて、より大きくパターンをずらすことができるのが特徴です。こちらも事前計算（いくつかのテーブル）が必要ですが、テキストポインタも前進します（ただし、比較は後ろから）。最悪ケースは O(nm) ですが、多くの場合の実用的な入力においては O(n/m) に近い性能を発揮します。
  • Rabin-Karp法: ハッシュ関数を利用した確率的なアルゴリズムです。パターンとテキストの各部分文字列のハッシュ値を比較することで高速化を図ります。ハッシュの衝突が発生する可能性があるため、衝突対策や追加の比較が必要ですが、特に多パターン検索において強力です。平均的には O(n+m) ですが、最悪ケースでは O(nm) になり得ます。

KMP法、Boyer-Moore法、Rabin-Karp法は、いずれも古典的かつ重要な文字列探索アルゴリズムであり、それぞれ異なるアプローチで効率化を実現しています。KMP法は、テキストの各文字を最大1回しか見ないという点で独自の特性を持ちます。

11. まとめ

KMP法は、Donald Knuth、James Morris、Vaughan Prattによって開発された、非常に効率的な文字列探索アルゴリズムです。単純な文字列探索アルゴリズムの非効率性を克服するために、不一致が発生した際にパターンをどれだけずらすべきかを、パターンの自己構造から導かれる「lps配列（または失脚関数）」を利用して決定します。

lps配列は、パターン中の各位置において、その位置で終わる接頭辞の中で最長の真の接頭辞かつ真の接尾辞である文字列の長さを格納します。この配列は、パターンの長さmに対してO(m)の時間で事前に計算可能です。

文字列探索フェーズでは、テキストとパターンを2つのポインタで走査します。文字が一致すれば両方のポインタを進めます。不一致が発生した場合、パターンポインタをlps配列の値に基づいて戻すことで、テキストポインタを後戻りさせることなく、効率的に次の比較位置へパターンをシフトさせます。パターン全体が一致した場合も、lps配列を利用して次のマッチの可能性を探るためにパターンポインタを更新します。

この巧妙な仕組みにより、KMP法は全体としてO(n+m)という線形時間での文字列探索を実現します。これは、特に長いテキストやパターンを扱う場合に、単純なO(nm)アルゴリズムと比較して圧倒的な速度向上をもたらします。ただし、lps配列のためのO(m)の追加空間が必要であり、アルゴリズムの理解・実装は単純な方法よりやや複雑になります。

KMP法は、その理論的なエレガンスと実用的な効率性から、コンピュータサイエンスにおける基本的なアルゴリズムとして広く学習され、テキスト処理、バイオインフォマティクス、ネットワークセキュリティなど、多岐にわたる分野でそのアイデアや直接的な応用が活用されています。文字列探索の分野を深く理解する上で、KMP法は避けて通ることのできない重要なアルゴリズムと言えるでしょう。

コメントする

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

上部へスクロール