文字列の頭良い感じの線形アルゴリズムたち

競プロ Algorithm

この記事はAdvent Calendar 2014の12/1の記事として書かれました。

はじめに

KMP、Manacher、Z algorithm の３つについて書きたいと思います。
１アルゴリズム／１日で追記して行きます。

これらのアルゴリズムでは「求めたいものの特性を生かして、既に計算した結果を上手に利用する」という点で共通しており、いずれも「なるほどなぁ」と言わされました。
この美しいアルゴリズムたちを是非紹介したいと思い、この記事を書くことにしました。

・記法について
|S|：文字列 S の長さを表す。
S[i,j]：文字列 S の i 文字目から j 文字目までを取り出した文字列を表す。

KMP

※これは正確にはKMPではなくMPです。KMPについてはこちら。
文字列 S が与えられたときに、各 i について「文字列S[0,i-1]の接頭辞と接尾辞が最大何文字一致しているか」を記録した配列を O(|S|)で構築するアルゴリズムです。ただし、|S[0,i-1]|未満のもののみを考慮します。
例えば、

aabaabaaa
_010123452

こんな感じです。(i=0の場所は適切な値が存在しないので_(-1の意味で使っています)とかを入れます。)
(等幅フォントじゃ無い場合は等幅フォントで見てね)

この配列を使うと文字列検索や周期性の判定などが高速に行えるようになるのですが、その辺りの説明は他のサイトにお任せします。

結論から言うと、MPのコードは以下のようになります。

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;
}

このコードが何をしているのかを見ていきます。

j の動きに注目します。各for文のステップを実行した後のjの場所を追ってみます。

S : abbabba
1 : ji_____
2 : j_i____
3 : _j_i___
4 : __j_i__
5 : ___j_i_
6 : ____j_i

j は A[i+1] を示しています。S[0:j-1]とS[i-j+1:i]は一致していますね。

S[i]とS[j]が一致していれば j++だけで事足ります。（上の例は基本的にj++ばっかりしてます）
しかし一致していなければそういうわけにはいきません。
一致しなかった時は１から計算し直せば正しい答えは得られますが、それだと効率が悪すぎます。
それを既に計算したものを利用してなんとかするのが whileの部分なのですが、「j = A[j]」というトリッキーなことをしています。

さっきの例は単純な例だったので、もう少し複雑な例を見てみましょう。

S : aabaabaaa
A : _010123452
7 : _____j_i_
8 : __j_____i

i=7,8のときだけpickupしました。
i が 8 になった瞬間は j は 5 で、while文に入ります。
while文では以下のような操作が行われます。

while (j >= 0 && S[i] != S[j]) j = A[j];
・i=8, j=5 ： S[8]=a,S[5]=b なので S[i] != [j]。jがA[j](=2)になる。
・i=8, j=2 ： S[8]=a,S[2]=b なので S[i] != [j]。jがA[j](=1)になる。
・i=8, j=1 ： S[8]=a,S[1]=1 なので S[i] == [j]。while文を抜けます。
（・while文を抜けた後 j++ されて j = 2 となります。）

ふーむ、なるほど？？

結局何をしているのでしょうか。

前のステップで緑の部分が一致していたとします。（二段目の緑の部分は S[0,A[i]-1]）
赤の文字と青の文字が同じなら j++ だけで良さそうですね。
赤の文字と青の文字が異なる場合、次にチェックすべきものは、

この図の緑(濃い方)の部分です。つまり、S[0,A[A[i]]-1]です。
ここまでの計算結果から、緑の部分は３つとも一致しているはずですね。
ここで赤の文字と青(濃い方)の文字が同じならば j = A[j], j++ とすればいいですね。
それで、赤の文字と青の文字が異なっていれば今度は S[0,A[A[A[i]]]-1] に注目して・・・とやっていけば良いというわけです。
イメージできましたでしょうか。

ここで、気になる計算量の方ですが、

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

一見２重ループなのでO(|S|^2)っぽく見えますね。
j の値に注目して解析してみます。j が変化する場所は以下の２カ所です。
・while文を１回回す度に j は必ず減る。(ただし -1 より小さくはならない)
・for文を１回回す度に j++ により j は 1 ずつ増える。
すると while が回る回数って合計で高々 O(|S|) 回になっていませんか？なぜなら、j の値を減らすためには j の値を増やさないといけないですが、j の増加分が |S| しかないからです。
こういう計算量解析うまいですよねー。

以上、MPでした。

次の記事（Manacher） | 次の次の記事（Z algorithm） | おまけ（KMP）