MP法とKMP法の違い

大学生なのでデータ構造とアルゴリズムという授業を取っているんですが、今まで自分がKMP法だと思い込んでいたものがMP法だった上、ネット上の記事が無限にバラバラなのでメモしておく。

MP法

MP法はMorris-Pratt algorithmと呼ばれるもので、Knuthが登場しない。

MP法では、パターン文字列に対してborderと呼ばれる値を計算することにより、シフト量を定める。

ある文字列Sのborderとは、Sの部分文字列であって、Sの接頭辞かつ接尾辞であるような文字列Wのことである。

MP法では、i=0..|S|に対して、S[0:i-1]の最長border(の長さ)をO(|S|)で求め、それを元にシフト量を決める。具体的な最長borderの求め方については、snukeのこの記事が一番分かりやすいのでこれを見るといいと思う。

snuke.hatenablog.com

さて最長borderが求まれば、1-originとして、j文字目で不一致した場合のシフト量はj-border[j]とすればよい(配列インデックスと何文字目を表すかのoriginの違いによって、±1となる可能性があるので気をつけること)。

結局、MP法とはどちらかというと、borderを計算することの出来る線形アルゴリズムという側面が強く、別に文字列検索にだけ使うようなものではない。

例えば検索文字列自体を検索する用途以外でMP法を使う例としては以下の問題などがある。

codeforces.com

KMP法

KMP法はMP法にKnuthがくっつくやつで(は？)、上記のborderによるシフト量の決定には、まだ定数の改善余地があるため、それを改善する。

ある文字列Sの、接頭辞Pを考える。

すなわち、S = P + Xである(ここで+は文字列のconcatenate)。

ただし、 PやXが空文字列であるとちょっと困るので、P' = P + '_', X' = X + '_'というように、末尾に番兵があることとする。

Pのtagged border(あるいはstrict border、strong borderともいう) Wとは、Pのborder Wであって、かつP[|W|] != X[0]であるものを指す。

MP法におけるシフトの何に無駄があるかというと、S[i:i+j]が、pat[:j]までのj文字が一致していて、S[i+j]とpat[j]で初めて不一致が起きた時、当然シフトが発生して、次は、pat[border[j]:]とS[i+j:]が一致しているかを比較し始めるわけだが、仮にpat[j] == pat[border[j]]であったとすると、このシフトはまだ不十分であるということになる。

なぜなら、今、不一致が起きたからS[i+j] != pat[j]であって、かつpat[j] == pat[border[j]]であるから、明らかにpat[border[j]] != S[i+j]となって、pat[border[j]:]とS[i+j:]は先頭からして一致しない。

よって、borderの中でも、P[|W|] == X[0]を満たすようなborderは文字列検索においては考えなくて良いことが分かり、そうでないようなborderの中で最長のものをシフト量の決定時に使えば、少し検索の定数が減ることが分かる。

実装はMP法からほとんど変わらないため、コストのかかる改善ではない。

例えば上記のsnukeのコードを、以下のように変更するだけでいい。

A[0] = -1;
int j = -1;
for (int i = 0; i < S.size(); i++) {
  while (j >= 0 && S[i] != S[j]) j = A[j];

  j++;
  // 元のコードでは A[i+1] = j;
  if (S[i+1] == S[j]) A[i+1] = A[j]; 
  else A[i+1] = j;
}

elseの部分は、元のコードと変わっていないので当たり前に受け取れる。

問題はif文の後のA[i+1] = A[j]という処理で、何故これでいいのかというと、

まず、帰納的に考えれば、j < i+1より、A[j]は既に正しく計算された値である。

したがって、S[A[j]] != S[j]が成立しており、S[i+1] == S[j]ならば、明らかにS[i+1] != S[A[j]]が成り立ち、MP法と同じ議論からこれは最長tagged borderでもある。

初め僕は「なんでwhileじゃなくてifなんだ？？」と思ってたけどまあこういう理由から、「A[i+1] = j; while (A[i+1] > -1 && S[i+1] == S[A[i+1]]) A[i+1] = A[A[i+1]];」とかしなくても良いということが分かる。

終わり。