KMP法（文字列検索）とは？仕組み・コード・計算量をわかりやすく解説

KMP法が解く問題

文字列検索は、短いパターンが長いテキストのどこに現れるかを求める問題です。素朴な方法では、すべての開始位置を試して文字を1つずつ比較します。通常のテキストでは高速ですが、繰り返しの多い入力では遅くなります。aaaaaaaaaa から aaaab を探すと、各位置でパターンのほぼ全体を比較することになり、計算量は O(n × m) です。

KMP法は、不一致の後にテキストの文字を読み直すことがありません。ドナルド・クヌース（Donald Knuth）、ジェームズ・H・モリス（James H. Morris）、ヴォーン・プラット（Vaughan Pratt）が、1977年に "Fast Pattern Matching in Strings" で発表しました。

考え方を言葉で説明すると

パターン ABABC を探していて、ABAB まで一致し、次のテキストの文字が C ではなかったとします。いま一致した ABAB は AB で終わっており、これはパターンの先頭と同じです。つまり、次の試行はすでに2文字が一致した状態から始まるとわかっているので、最初からやり直さず、パターンの位置2から比較を続けられます。

プレフィックス関数は、これらの数を保存します。pi[i] は、pattern[0..i] の真の接頭辞（真とは、文字列全体ではないという意味です）のうち、その接尾辞にもなっている最長のものの長さです。

たとえば、ABABA は ABA で始まり ABA で終わるので pi[4] = 3 です。ABABAC の接頭辞で C で終わるものはないので pi[5] = 0 です。

具体例で一歩ずつ確認

テキスト ABABABC から、パターン ABABC（プレフィックス関数は 0, 0, 1, 2, 0）を探します。変数 k は、現在一致しているパターンの文字数を数えます。

テキスト側のポインタは7回前進し、一度も後戻りしませんでした。素朴な方法では位置1からやり直し、いくつかの文字をもう一度比較することになります。

Pythonでの実装

def prefix_function(p):
    pi = [0] * len(p)
    k = 0
    for i in range(1, len(p)):
        while k > 0 and p[i] != p[k]:
            k = pi[k - 1]          # fall back to a shorter border
        if p[i] == p[k]:
            k += 1
        pi[i] = k
    return pi

def kmp_search(text, pattern):
    """Return the start index of every occurrence (overlaps included)."""
    if not pattern:
        return []
    pi, k, hits = prefix_function(pattern), 0, []
    for i, ch in enumerate(text):
        while k > 0 and ch != pattern[k]:
            k = pi[k - 1]
        if ch == pattern[k]:
            k += 1
        if k == len(pattern):
            hits.append(i - k + 1)
            k = pi[k - 1]          # keep going to find overlapping matches
    return hits

print(prefix_function("ABABACA"))      # [0, 0, 1, 2, 3, 0, 1]
print(kmp_search("ABABABC", "ABABC"))  # [2]
print(kmp_search("AAAAA", "AA"))       # [0, 1, 2, 3]

時間計算量と空間計算量

素朴なアルゴリズムは最悪 O(n × m) ですが、自然言語のテキストでは O(n) に近いことが多く、KMP法の利点が目立つのは主に繰り返しの多いデータです。

バリエーションとよくある間違い

• フォールバックでの1つのずれ：不一致の後は k = pi[k] ではなく k = pi[k - 1] にします。pi は、最後に一致した位置で添字を付けるためです。
• フォールバックに while ではなく if を使う：文字が一致するまでに、連続して何度かフォールバックが必要になることがあります。
• 完全一致の後に k をリセットし忘れる：重なる一致も見つけるには k = pi[k - 1] に、重ならない一致だけなら k = 0 に設定します。
• 連結のテクニック：pattern + separator + text のプレフィックス関数を計算します。区切り文字には、どちらにも現れない文字を使います。値が m に等しい位置はすべて、一致の終端です。
• Zアルゴリズムは、これとよく似た配列を計算し、同じく O(n + m) で検索できます。

使う場面と実世界での用途

• コーディング面接の問題：strStr() の実装、最短の回文（s + "#" + reversed(s) のプレフィックス関数）、繰り返し部分文字列パターン、文字列の最小周期（m - pi[m - 1]）。
• 実世界：DNA配列やネットワークパケットのストリームの検索など、最悪時の線形時間が重要な場面。