クヌース–モリス–プラット法

クヌース–モリス–プラット法 (KMP法) は文字列探索アルゴリズムの一種で、発明者3名の名前を冠しています。 力まかせ探索に比べ、余計な探索(比較)をしないような工夫をすることで、計算量 O(N) を実現します。

このアルゴリズムでは、複数回文字への探索(比較)をしないようにあらかじめ、部分マッチ用の表を作成しておく必要があります。この前処理や複雑な処理のせいで単純な力まかせ探索に比べ、余計なオーバーヘッドが発生し、実用上力まかせ探索より処理速度が遅くなったりもします。ですが理論上は高速です。

特徴

以下の表は力まかせ探索で "AABABBABABCAB" から "ABABCA" を探索する場合のものです。2回目(2文字目から)の比較で6文字目 の "B" まで探索(比較)しているのに、マッチしないので3文字目からやり直しています。この比較位置の後戻りが無駄な処理として効率化できるということで、理論上はより高速に動作します。

A A B A B B A B A B C A B
1 A B
2 A B A B C
3 A
4 A B A
5 A B
6 A
7 A B A B C A

本来上記の例では3回目の探索で、探索対象文字の7文字目まで比較したのだから、その情報を持って、7文字目からパターン文字との比較を再開すべきです。もちろん4回目以降の探索でも同様です。探索対象文字列の比較位置を後戻りしないように工夫すると、次の表のような比較順序になります。

A A B A B B A B A B C A B
1 A B
2 A B A B C
3 A B A
4 A B A B C A

一度進めた探索対象文字列の位置が後戻りしないため効率的な探索を可能にしているのが見て取れます。灰色の文字は実際には探索(比較)せず、この位置にあることがわかるのでパターン3文字目の "A" から探索を再開しています。

不一致が起こった際、探索対象文字列の比較位置はそのままにします。対してパターンの比較位置を何文字目から比較するかで無駄な処理を省きます。例えば上記の例だと、パターン "ABABCA" の5文字目 "C" が不一致の場合、パターンを3文字目の "A" の探索(比較)から処理を再開することができます。なぜなら "ABAB" までは一致しているため、2回目に出てきている "AB" 部分を 先頭の "AB" 部分として考えることができるからです。つまり3文字目 "A" の探索(比較)から処理を再開できるのです。

もちろん探索開始前に、パターン文字列において不一致になった文字(位置)ごとに、パターン文字の比較再開位置(ずらし位置)を保持した対照表を用意しなければなりません。これをずらし表と呼ぶことにします。

ずらし表

ずらし表の作成には、パターン文字列に対してパターン文字列自身を比較することで求まります。

A B A B C A
A
A B A
A
0 0 0 1 2 0

この表はパターン文字列 "ABABCA" について2文字目から自身の文字列と比較していきます。一致しない時点で何文字一致していたかが、ずらし位置です。1文字目は当然ずらすので0とします。

パターン文字列との比較時点で直前までに何文字一致していたかがずらす数になります。表の最終行の数がそれです。例えば、"C" で不一致があった場合、パターンの2文字前の "A" まで戻り探索(比較)を再開します。上の比較順序の表と見比べてその意味を理解する必要があります。

アルゴリズムの解説

  1. 探索するパターン文字列からずらし表を生成します。
  2. 探索対象文字列上の位置を i=0 , パターン文字列上の位置を p=0 とします。
  3. i, p がそれぞれ探索対象文字列, パターン文字列の文字数を越えない条件でループします。
    • 探索対象文字列i文字目とパターン文字列p文字目を比較します。
    • 一致していた場合、 iとp を 1進めます。
    • p=0(パターン先頭文字) で不一致の場合、i を1進めます。
    • その他(不一致)の場合、pをずらし表から取得した位置にします。
  4. パターン全文字に一致していれば i 、一致していなければ -1 を結果として返します。

サンプルコード

C#

// クヌース・モリス・プラット法(KMP探索)
public int KMPSearch(string target, string pattern)
{
    // ずらし表の作成
    var table = CreateTable(pattern);

    // 文字列探索
    int i = 0, p = 0;
    while (i < target.Length && p < pattern.Length)
    {
        if (target[i] == pattern[p])
        {
            // 文字が一致していれば次の文字に進む
            i++; p++;
        }
        else if (p == 0)
        {
            // パターン先頭文字が不一致の場合、次の文字
            i++;
        }
        else
        {
            // 不一致の場合、パターンのどの位置から再開するか設定
            p = table[p];
        }
    }
    if (p == pattern.Length)
    {
        return i - p;
    }
    return -1;
}

// ずらし表の生成
public int[] CreateTable(string pattern)
{
    var table = new int[pattern.Length];
    table[0] = 0;

    var j = 0;
    for (int i = 1; i < pattern.Length; i++)
    {
        if (pattern[i] == pattern[j])
        {
            table[i] = j++;
        }
        else
        {
            table[i] = j;
            j = 0;
        }
    }
    return table;
}