クヌース・モリス・プラット（KMP）法とは？最悪計算量O(n)の文字列検索アルゴリズムを解説

Knuth–Morris–Pratt法（KMP法）は、テキストを左から右へ向かって一方向に走査しながらパターン照合を行う、高速な文字列検索アルゴリズムです。照合中に不一致が発生した際にも、それまでに一致済みだった文字の情報を捨てずに再利用するため、テキスト側の比較位置を後戻りさせる必要がありません。とくに、パターンの中に同じ部分文字列（サブパターン）が複数回現れるような場合、その性質を活かして無駄な比較を大幅に削減でき、最悪の入力に対しても安定した性能を発揮します。

その計算量は O(n)（nはテキスト長。厳密には前処理を含めて O(n + m)、mはパターン長）であり、どのような入力でも線形時間で完了する点が最大の強みです。

入力と出力

ここでは、主文字列「AAAABAAAAABBBAAAAB」からパターン「AAAB」を検索する例を扱います。

入力:
主文字列: "AAAABAAAAABBBAAAAB"
パターン: "AAAB"

出力:
パターンの一致位置: 1
パターンの一致位置: 7
パターンの一致位置: 14

アルゴリズムの考え方

KMP法は、次の2つの段階で構成されます。

1. 前処理： パターン自身から「接頭辞関数」（失敗関数とも呼ばれます）を作成します。これは、各位置までの部分文字列において「先頭からの接頭辞」と「末尾の接尾辞」が一致する最大の長さを記録した表です。
2. 検索： テキストとパターンを比較し、不一致が起きたときに接頭辞関数を参照してパターン側の再開位置を決めます。これにより、一致済みの部分を調べ直すことなく検索を続行できます。

接頭辞関数の構築：findPrefix(pattern, m, prefArray)

入力 − パターン、パターンの長さ m、接頭辞の長さを格納する配列

出力 − 各位置における最長接頭辞の長さを格納した配列

length := 0
prefArray[0] := 0

パターンの各文字インデックス i について繰り返す
    if pattern[i] = pattern[length] then
        length := length + 1
        prefArray[i] := length
    else
        if length ≠ 0 then
            length := prefArray[length - 1]
            i := i - 1
        else
            prefArray[i] := 0

本体：kmpAlgorithm(text, pattern)

入力: 主テキストと、検索対象となるパターン

出力 − パターンが見つかった位置の一覧

n := テキストの長さ
m := パターンの長さ
findPrefix(pattern, m, prefArray) を呼び出す

while i < n do
    if text[i] = pattern[j] then
        i と j を 1 ずつ増やす
    if j = m then
        位置 (i - j) にパターンが見つかったものとして出力
        j := prefArray[j - 1]
    else if i < n AND pattern[j] ≠ text[i] then
        if j ≠ 0 then
            j := prefArray[j - 1]
        else
            i := i + 1

C++による実装例

以下は、上記のアルゴリズムをC++で実装したコード例です。

#include<iostream>
using namespace std;

// 接頭辞（失敗）配列を構築する
def findPrefix(string pattern, int m, int prefArray[]) {
    int length = 0;
    prefArray[0] = 0;      // 先頭は常に0（対応する接頭辞がないため）

    for(int i = 1; i<m; i++) {
        if(pattern[i] == pattern[length]) {
            length++;
            prefArray[i] = length;
        }else {
            if(length != 0) {
                length = prefArray[length - 1];
                i--;     // 反復後のインクリメントを打ち消すため i を減らす
            }else
                prefArray[i] = 0;
        }
    }
}

// KMP本体：パターン検索を行う
void kmpPattSearch(string mainString, string pattern, int *locArray, int &loc) {
    int n, m, i = 0, j = 0;
    n = mainString.size();
    m = pattern.size();
    int prefixArray[m];     // パターンと同じサイズの接頭辞配列
    findPrefix(pattern, m, prefixArray);
    loc = 0;

    while(i < n) {
        if(mainString[i] == pattern[j]) {
            i++; j++;
        }

        if(j == m) {
            locArray[loc] = i-j;      // 位置 i-j でパターンが見つかった
            loc++;
            j = prefixArray[j-1];     // 配列から接頭辞の長さを取得して再開
        }else if(i < n && pattern[j] != mainString[i]) {
            if(j != 0)
                j = prefixArray[j-1];
            else
                i++;
        }
    }
}

int main() {
    string str = "AAAABAAAAABBBAAAAB";
    string patt = "AAAB";
    int locationArray[str.size()];
    int index;
    kmpPattSearch(str, patt, locationArray, index);

    for(int i = 0; i<index; i++) {
        cout << "Pattern found at location: " <<locationArray[i] << endl;
    }
}

実行結果

Pattern found at location: 1
Pattern found at location: 7
Pattern found at location: 14

主文字列中の位置 1、7、14 の3か所でパターン「AAAB」が検出されました。KMP法ではテキストの走査が常に一方向に進むため、テキスト長を n とすると、最悪の場合でも比較回数は線形オーダー O(n) に収まります。素朴な文字列検索（ナイーブ法）が最悪 O(n × m) かかることを考えると、長いテキストや反復的なパターンを扱う場面で、その効果は絶大です。