KMP法
テキスト文字列 txt
にパターン文字列 pat
が現れる位置を求めます。
たとえば txt = "abaaaba", pat = "aab"
のとき、テキストの $4$ 文字目からパターンが現れます。
abaaaba aab
素朴な方法として、パターンの開始位置を全通り試すというものがあります。
上と同じ例でテキストの $i$ 文字目 ($i = 1, 2, 3, 4$) とパターンの先頭を揃え、テキストの文字と異なる文字が現れるまでパターンを読んでいくと次のようになります。
x
は初めてテキストの文字とパターンの文字が異なった位置を示しています。
abaaaba ax x aax aab
一般に、テキストの長さを $N$、パターンの長さを $ M $ とすると、素朴な探索法では文字の比較回数が最悪で $NM$ 回ほどになりえます。
具体的には txt = "aaaaaaaaaaaaaab", pat = "aaaaab"
のようなケースが該当します。
パターンとの照合をテキストの $1$ 文字目から始めると $5$ 文字目までは互いの文字が一致しているので、リーチの状況まで持っていけます。
aaaaaaaaaaaaaab aaaaa_
あと $1$ 文字一致すれば晴れてテキスト内のパターン出現位置が特定できることになりますが、現実は非情でパターンの $6$ 文字目 (_
に入る文字) は b
、テキストの $6$ 文字目は a
なので異なる文字です。
テキストの $1$ 文字目から始まる文字列はパターンに一致しないことが分かりました。
そこで次はテキストの $2$ 文字目から始めて、パターンの先頭から $1$ 文字ずつ比較していきましょう。
しかしこの場合も先ほどと同様にリーチまではたどり着くものの、最後の $1$ 文字というところで不一致になってしまいます。
この繰り返しが $N - M + 1$ 回起こるため全体で $ (N - M + 1)M $ 回ほど文字の比較を行うことになります。
ふつう、テキストはパターンより十分長いため $NM$ に対して $M^2$ は無視できるほど小さいです。
したがって、素朴な方法の場合、特定のケースでは約 $NM$ 回の比較が必要になることが分かりました。
KMP 法はこのようなケースも含めて、文字の比較回数を最悪で $ N + M $ 回程度に抑えます。
上の方法では、テキストの文字とパターンの文字が不一致になったとき、それまで一致してきた文字数に関係なく一律でカーソル (テキストやパターンの見ている位置) をリセットしていました。
一致した文字数が少ない場合は、まあ仕方ないかと思えますが、たくさん一致していた場合はどこかもったいない気がしてきます。
実は、テキストのカーソルを戻すことなく、パターンの出現位置を検出することができます (パターンのカーソルはいくらか戻ります) 。
txt = "abababaabba", pat = "ababaabb"
とします。
テキストの $1$ 文字目から照合を始めると、$6$ 文字目で初めて不一致が起こります。
v abababaabba ababax ^
このとき、カーソルはテキスト・パターンともに $6$ 文字目を指しています。
ここでテキストのカーソルを $2$ 文字目に、パターンのカーソルを $1$ 文字目に戻すのが素朴な探索法でした。
v ababababba _ ^
テキストのカーソルを動かさずに、パターンのカーソルのみを戻すことで照合を再開したいです。
$1$ 文字分だけカーソルを戻してみましょう。
カーソルは固定されていて、パターンの文字列全体を右に $1$ 文字分ずらすと考えてもいいです。
v ababababba abab_ ^
_
はその文字をまだ見ていない (見る直前である) ことを示しています。
カーソルが指す文字同士を比較する以前に、この照合は失敗することが分かります。
なぜなら、長さ (文字数) $n$ の文字列同士が一致することは、先頭 $n - 1$ 文字が一致してさらに $n$ 文字目も同じ文字であることと同等だからです。
いまの場合、_
より左の $4$ 文字すべてがテキストの対応する位置にある文字と一致している必要がありますが、そうなっていません。
それでは、パターンのカーソルを $2$ 文字分戻してみましょう。
v ababababba aba_ ^
幸運なことに、パターンの先頭から $3$ 文字 (_
までは達しない長さ) がテキストと一致しています。
したがって、照合はパターンの $4$ 文字目から始めればいいです。
$4$ 文字目が同じ文字なら次の文字 ($5$ 文字目) を比較し、そうでないならさらにパターンのカーソルを戻します。
このようにすれば、テキストのカーソルを動かすことなくテキストとパターンの照合を行うことができます。
上の例 (txt = "ababababba", pat = "ababaabb"
) では $6$ 文字目で不一致が起こった際に、パターンのカーソルを $2$ 文字分戻す必要がありました。
そうすることで、カーソル位置の直前までの (カーソルが指す文字を含まない) 文字列と、対応する位置にあるテキストの文字列が一致するのでした。
このようなカーソルの位置を見つけるにはどうしたらいいのでしょうか。
確実な方法は、例で行ったようにカーソルを $1$ つずつずらしていき、そのたびに条件を満たすかチェックするというものです。
しかし文字列同士の一致を判定するには、文字列の長さと同じ回数だけ文字を比較しなければいけません。
すると結局は、最悪の場合に全体で $NM$ 回程度の比較が必要になり、本末転倒感があります。
この問題を回避するために、パターンのカーソルが移動すべき位置について整理しましょう。
やはり上の例で $6$ 文字目に不一致が見つかった時点を考えます。
パターンのカーソルを $2$ 文字分戻すことは、パターン自身を右に $2$ 文字分ずらすことと同じでしたから次のようになります。
テキストの $6$ 文字目以降は気にしなくていいので省略しています。
ababa ababa
ここで "aba"
が "ababa"
(パターンの先頭から $5$ 文字を切り出した文字列) の prefix*1 であり suffix*2 でもあることに気づくかと思います。
この特徴は $1$ 文字ずらしのときには現れていません。
ababa ababa
"ababa"
の prefix であり suffix でもあるような文字列で、長さが $4$ のものは存在しないからです。
したがって、カーソルの移動先を知るには $ j = 1, 2, \dots, M $ について
$\mathrm{next}[j] := $「パターンの先頭 $j$ 文字を切り出した文字列」の prefix であり suffix でもある文字列の最大長 (文字数)
が分かっていればいいです (ただし、prefix および suffix として文字列全体を取るのは禁止です) 。
実際、文字の不一致が起こったときに、パターンのカーソルが 0-indexed で $j$ 番目の文字を指していたとすると、次のカーソル位置として $\mathrm{next}[j]$ を選べます。
このときテキストのカーソルが $i$ 番目の文字を指していたとすると、テキスト上の $i$ の左隣り $\mathrm{next}[j]$ 文字は $\mathrm{next}[j]$ の定義より、パターン上の $\mathrm{next}[j]$ の左隣り $\mathrm{next}[j]$ 文字と一致しています。
よって $\mathrm{next}[j]$ はカーソルの移動先として適切です。
pat = "ababaabb"
に対する $\mathrm{next}[]$ 配列を以下の表に示します。
j | next[j] | パターンの先頭 j 文字 |
---|---|---|
0 | -1 | |
1 | 0 | a |
2 | 0 | ab |
3 | 1 | aba |
4 | 2 | abab |
5 | 3 | ababa |
6 | 1 | ababaa |
7 | 2 | ababaab |
8 | 0 | ababaabb |
実装の都合上 $\mathrm{next}[j] = -1$ としておくといいです。
テキスト文字列 txt
とパターン文字列 pat
を受け取って、テキスト内にパターンが最初に現れる位置 (存在しなければ $-1$) を返す関数 kmp_search
は次のように実装できます。
int kmp_search(const string &txt, const string &pat) { vector<int> next = build_next(pat); int i = 0, j = 0; while (i < txt.size() and j < pat.size()) { while (j >= 0 and txt[i] != pat[j]) { j = next[j]; } i += 1; j += 1; } if (j == pat.size()) { return i - j; } else { return -1; } }
内側の while
を抜けた直後は j == -1
または txt[i] == pat[j]
です。
後者は分かりやすいと思います。
パターンの先頭 $j$ 文字の照合が完了していて、0-indexed で $j + 1$ 番目の文字も一致した (txt[i] == pat[j]
) という状況です。
次の文字を比較するためにテキストのカーソルとパターンのカーソルを $1$ つずつ進めます (i += 1; j += 1;
) 。
前者について考えます。
while
内部の j = next[j];
はパターンのカーソルを左に動かす処理でした。
しかし、カーソルを戻せる範囲にも限界があります。
具体的にはパターンの先頭まで、つまり $j = 0$ までです。
先頭まで戻ってきて pat[0]
とテキストのカーソルが指している文字 txt[i]
を比較しますが、これすら異なっていたらもはやできることはありません。
次の比較では txt[i + 1]
と pat[0]
をチェックしたいです。こちらならまだ可能性があります。
while
のあとにインクリメントされることを考えると、$i$ はそのままにしておき、$j$ には $-1$ をセットすべきです。
ちょうど next[0]
には意味のある値は入っていません。
ここに $-1$ を格納しておけば、しかるべきときに $j$ へ $-1$ が代入 (j = next[0];
) されます。
$j$ がひとたび $-1$ になったらすぐに while
を抜けるように (j >= 0
) しておきましょう。
例として txt = "abbaba", pat = "aba"
のとき、プログラムの動作をトレースしてみます。
序盤は省略しますが、$i = 2, j = 2 $ になってはじめて内側の while
文の中身が実行されます。
以下は txt[2] != pat[2]
を示した図です。
abbaba abx
$\mathrm{next}[2] = 0$ なので j = next[j];
によって $j$ に $0$ が代入されます。
さらに txt[2] != pat[0]
なのでもう一度 j = next[j];
が実行され、$j$ に $-1$ が代入されて while
を抜けます。
while
を抜けたあと $i, j$ はインクリメントされ、$i = 3, j = 0$ になっています。
以下は、次回のループで txt[3]
と pat[0]
が比較される予定を示した図です。
abbaba _
残るはパターン文字列 pat
から $\mathrm{next}[]$ 配列を生成する build_next
関数の実装です。
とは言っても、kmp_search
関数とほぼ同じ見た目になります。パターン自身と照合させるイメージです。
$i$ の小さい順に $\mathrm{next}[i]$ を順次確定させていきます。
$i = 0$ については $\mathrm{next}[0] = -1$ とするのでした。
また、つねに $\mathrm{next}[1] = 0$ が成り立ちます。
長さ $1$ の文字列において全体と一致しない prefix (および suffix) は空文字列のみだからです。
$\mathrm{next}[i]$ は最大でも $i - 1$ にしかならないのでその範囲を全てチェックすれば確実に $\mathrm{next}[i]$ を求めることができます。
しかし、さらに考えると $\mathrm{next}[i]$ は $\mathrm{next}[i - 1]$ から最大でも $+1$ しかされないことが分かります。
これは前述のように、文字列の一致についてstep by step な構造があるからです。
つまり、$\mathrm{next}[i] = \mathrm{next}[i - 1] + 1$ となるのは、パターンの $i - 1$ 番目の文字と $\mathrm{next}[i - 1]$ 番目の文字とが一致するときに限ります。
それぞれの文字は「パターンの先頭 $i$ 文字を切り出した文字列」における長さ $\mathrm{next}[i]$ 文字の suffix の末尾、prefix の末尾です。
たとえば pat = "ababaabb"
とします。
このとき $\mathrm{next}[5] = \mathrm{next}[4] + 1 = 3$ でした。
この値が確定する直前の様子は次のように表せます。配列の添字が $0$ 始まりであることに注意してください。
ababa ab_
次に $\mathrm{next}[i]$ が $\mathrm{next}[i - 1]$ から増加しない場合を考えましょう。
これはちょうど次のような状況です。注目している位置以降は .
で表しています。
ababaa abab..
「パターンの先頭 $6$ 文字を切り出した文字列」において、末尾 $4$ 文字と先頭 $4$ 文字が一致していません。
しかし、一歩手前では "aba"
(先頭 $5$ 文字からなる文字列における長さ $\mathrm{next}[5] = 3$ の prefix = suffix) が一致していたわけですから、これを利用しましょう。
"aba"
はパターンの先頭 $3$ 文字を切り出した文字列とも考えられ、$\mathrm{next}[3]$ がすでに求まっており、その値は $1$ です。
したがって、"aba"
の先頭 $1$ 文字と末尾 $1$ 文字は一致していて、これは "ababa"
(パターンの先頭 $5$ 文字を切り出した文字列) に対しても成り立ちます。
そこでパターンの $5$ 番目の文字 pat[5]
と $\mathrm{next}[\mathrm{next}[5]]$ 番目の文字 pat[1]
を比べます。
これらが等しければ $\mathrm{next}[6] = \mathrm{next}[\mathrm{next}[5]] + 1$ と確定できます。
しかし以下の図で見るように pat[5] = 'a', pat[1] = 'b'
であり、異なる文字です。
ababaa abab.. ab....
そうすると、次は "a"
をパターンの先頭 $\mathrm{next}[\mathrm{next}[5]] = 1$ 文字を切り出した文字列とみなして、同様の手順を実行します。
$\mathrm{next}[1] = 0$ が分かっているので、pat[5]
と pat[0]
を比べればいいです。
そして、この比較は成功します。
ababaa abab.. ab.... a.....
最終的に $\mathrm{pat}[6] = 0 + 1$ が確定します。
$+1$ は注目している文字が一致した分で、$0$ はその文字より左で一致している長さの分です。
build_next
関数の実装例を以下に示します。
vector<int> build_next(const string &pat) { vector<int> next(pat.size() + 1); int i = 0, j = -1; next[i] = j; while (i < pat.size()) { while (j >= 0 and pat[j] != pat[i]) { j = next[j]; } i += 1; j += 1; next[i] = j; } return next; }
kmp_search
ではテキストとパターンの先頭同士から比較を開始していましたが、こちらでは $1$ 文字ずらして始めないといけません。
文字列全体を prefix (suffix) とみなさないためです。
したがって、下図のように pat[0]
と pat[1]
の比較から始めます。
ababaabb _
内側の while
を抜けた直後は、
pat[j] == pat[i]
pat[j - 1] == pat[i - 1]
- ...
pat[0] == pat[i - j]
が満たされています。
つまり、「パターンの先頭 $i + 1$ 文字を切り出した文字列」において長さ $j + 1$ の prefix と suffix は一致しています。
pat[0]
から pat[i]
までには $i + 1$ 文字存在することに注意してください。
最後に kmp_search
の計算量を考えます。
ループの最も内側の j = next[j];
が関数全体で実行される回数 $n$ を評価すればいいです。
$j$ の増減に注目すると、はじめ $j = 0$ で、j += 1;
が実行されると $1$ 増え、j = next[j];
が実行されると $1$ 以上減ります ($\mathrm{next}[j] < j$ だからです) 。
そして外側の while
を抜けた時点で $j$ は $0$ 以上です。
外側のループは最大 $N$ 回 (テキストの長さと同じ回数) 回るので、少なくとも $n \le N$ でないといけません。
したがって kmp_search
関数の計算量は $O(N)$ と分かりました。
build_init
関数についても同様の解析によって $O(M)$ であることが分かります。
よって、KMP法全体での計算量は $O(N + M)$ です。