KMP 法について - mayoko’s diary

文字列処理アルゴリズム全然知らないので調べてみることにしました。とりあえず KMP 法について書きたいと思います。

そもそも KMP 法とは

KMP 法は, 文字列 S (sentence?) の中で, 文字列 W(word?) が現れる場所を列挙するアルゴリズムです。

例えば, S = "abababa", W = "aba" だったら, S の中に W が現れる場所は, 0, 2, 4 の 3 つです。また, S = "ABCXABCDABXABCDABCDABDE", W = "ABCDABD" の時は, S の中に W が現れるのは, S の 14 文字目からです(0-index)。

KMP 法の構成

とりあえず最初に自分の KMP 法ライブラリを貼っておきます。

// kmp をやるための前計算
vector<int> makeTable(const string& s) {
    int n = s.size();
    vector<int> ret(n+1);
    ret[0] = -1;
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && s[i] != s[j]) j = ret[j];
        ret[i+1] = ++j;
    }
    return ret;
}

// str の中に word とマッチする場所のリストを返す
// ret のそれぞれの要素 el は, 「str[el] からの文字列が word と一致する」ことを示す
vector<int> kmp(const string& str, const string& word) {
    vector<int> table = makeTable(word), ret;
    int m = 0, i = 0, n = str.size();
    while (m+i < n) {
        if (word[i] == str[m+i]) {
            if (++i == (int)(word.size())) {
                ret.push_back(m);
                m = m+i-table[i];
                i = table[i];
            }
        } else {
            m = m+i-table[i];
            if (i > 0) i = table[i];
        }
    }
    return ret;
}

KMP 法は 2 段階のアルゴリズムから構成されます。一つは文字列 W を使って前計算をするフェイズ(makeTable っていう関数でやってるところ), もうひとつはその前計算でメモしたものを使って S から W にマッチする場所を探すフェイズ(kmp でやってるところ)です。

前計算するフェイズ

前計算では, 文字列 W が与えられたときに、各 i について「文字列 W[0,i-1] の接頭辞と接尾辞が最大何文字一致しているか」を記録した配列 table を O(|W|) で構築するアルゴリズムです。ただし, 各 i について, 一致している文字数が i になるものが必ず存在しますが, これは除きます(これを除かないと任意の i について table[i] = i となって意味がないので)。
あと念の為ですが, "abcd" の接頭辞は "a", "ab", "abc", "abcd" で, 接尾辞は "d", "cd", "bcd", "abcd" ですね。

このアルゴリズムについては snuke さんの記事がわかりやすいのでそちらを読むのをオススメします(一応こっちでも書きますが)。
snuke.hatenablog.com

makeTable では, "それまでの計算結果を利用" することがポイントです。もう一度コードを載せておきます。

// kmp をやるための前計算
vector<int> makeTable(const string& s) {
    int n = s.size();
    vector<int> ret(n+1);
    ret[0] = -1;
    int j = -1;
    for (int i = 0; i < n; i++) {
        while (j >= 0 && s[i] != s[j]) j = ret[j];
        ret[i+1] = ++j;
    }
    return ret;
}

今, 0, 1, ..., i までの table の値がわかっているとしましょう。この時, table[i+1] の値を求めたいです。

まず, table[i] の値がわかっているので,
W[0,table[i]-1] と W[i-table[i]+1, i] 文字列は一致しています。これで, W[table[i]] と W[i+1] が一致していれば, table[i+1] = ++j して終わりです。一方で, 一致していなかった場合は, j の値はもっと少なくなるはずです。どこまで少なくなるのかを考えたいです。

必要条件で考えてみます。
「W の最初の j 文字」と「W[i+1] までの j 文字」が一致しているためには, 少なくとも「W の最初の j-1 文字」と「W[i] までの j-1 文字」が一致していないとダメですね(上で table[i] を利用して答えを求めようとしている時も, この論理を使っている)。

ここから先は自分で図を書くか, snuke さんの記事の図とにらめっこしながら読むことをオススメします。
この「『W の最初の j-1 文字』と『W[i] までの j-1 文字』が一致している」の j の候補ですが, table[i] によって「『W の最初の table[i] 文字』と『W[i] までの table[i] 文字』が一致している」という情報がわかっているので, 「『W の最初の j-1 文字』と『W[table[i]-1] までの j-1 文字』が一致する」ことがわかります。
これはつまり, j の次の候補は table[table[i]] である, ということを示しているので, これを調べます。これでもダメなら table[table[table[i]]] を調べる…と続きます。これで j の候補はすべて挙げられるので, 上のプログラムでキチンと動くわけです。

後は計算量解析です。

j は -1 未満にならない
j は for 文を一回回すごとに 1 だけ増える

ということを考えると, j は O(|W|) 分しか変化しないので, 計算量は O(|W|) です。

実際に計算するフェイズ

こっちのほうが簡単です。ソースコードを再掲します。

// str の中に word とマッチする場所のリストを返す
// ret のそれぞれの要素 el は, 「str[el] からの文字列が word と一致する」ことを示す
vector<int> kmp(const string& str, const string& word) {
    vector<int> table = makeTable(word), ret;
    int m = 0, i = 0, n = str.size();
    while (m+i < n) {
        if (word[i] == str[m+i]) {
            if (++i == (int)(word.size())) {
                ret.push_back(m);
                m = m+i-table[i];
                i = table[i];
            }
        } else {
            m = m+i-table[i];
            if (i > 0) i = table[i];
        }
    }
    return ret;
}

コードでは, m が「S のどこを指し示しているか」に関する変数です。すなわち, 「今は m から始まる|W| 文字が W と一致しているか調べようとしているぞ」ということです。で, i が「今 W の何文字目を調べているか」を示す変数です。W[i] == S[m+i] なら ++i とやっているのは「W の i 文字目と今調べているところは一致しているから次進んで良いよね」ということです。

なんとなくコードを察したところで具体例を見てみましょう。

文章 S の中からある単語 W を探します。仮に W = "tartar" であるとしましょう。この時, table を求めると,
table[0] = -1, table[1] = 0, table[2]= 0, table[3] = 0, table[4] = 1, table[5] = 2, table[6] = 3 です。
"t" で食い違った場合
次の文字から調べれば OK ですが, m = m+i-table[i] = m+0-(-1) = m+1, i=0 となっているので, 確かに次の文字から調べることになっています。
"t" は OK で "a" で食い違った場合
"t" を飛ばして次の文字から調べれば OK ですが, m = m+i-table[i] = m+1-0 = m+1, i=table[i]=0 となっているので, 確かに次の文字から調べることになっています。
"ta" は OK で "r" で食い違った場合
"ta" を飛ばして次の文字から調べれば OK ですが, m = m+i-table[i] = m+2-0 = m+2, i=table[i]=0 で OK です。
"tar" は OK で "t" で食い違った場合
上と同様です。m=m+3,i=0 となります。
"tart" は OK で "a" で食い違った場合
この場合は今までとは違います。2 回目の t を飛ばしてしまうと, その 't' から始まる W を見逃してしまう可能性があるので, この場合は 2 回目の 't' から探索を再開します。ここで, "tart" の接頭辞と接尾辞は 1 文字一致している(table[i]=1) であることに注意です。
m = m+i-table[i] = m+4-1 = m+3, i=table[i]=1 より, 確かに最初の 't' を飛ばして探索を続行しています。
"tarta" は OK で "r" で食い違った場合
やはり 2 回目の 't' から探索を再開するのが良いですが, "tarta" の接頭辞と接尾辞が一部一致しているので, m = m + (一致していた文字数) - (table[i]), i = table[i] とするのが良いことがわかります。

最後に計算量解析です。今回は m という量と m+i という量に注目します。

S[m+i] == W[i] が成り立った場合, m は変化せず i は 1 足されます。よって, m+i は増加します。
S[m+i] == W[i] が成り立たなかった場合, m = m+i-table[i] となりますが, 常に table[i] < i が成り立つので, m は増加します。

m, m+i はどちらもたかだか |S| なので, このアルゴリズムはたかだか 2*|S| 回でループを抜けます。よって, 計算量は O(|S|) です。

以上, KMP 法でした。