昨日の記事の続きです。
Z algorithm
文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。
例えば、
aaabaaaab 921034210
こんな感じです。
Z algorithmのテクニックはManacherとよく似ています。ですので、以下の解説記事を読む前に少し考えてみると分かるかもしれません。
さて、結論から言うと、Z algorithmのコードは以下のようになります。
A[0] = S.size(); int i = 1, j = 0; while (i < S.size()) { while (i+j < S.size() && S[j] == S[i+j]) ++j; A[i] = j; if (j == 0) { ++i; continue;} int k = 1; while (i+k < S.size() && k+A[k] < j) A[i+k] = A[k], ++k; i += k; j -= k; }
Manacherのコードとよく似ていますね。
ベースとなるアイデアについて見てみましょう。
キーワードは「既に計算したものを利用する」です。
緑の文字列が一致していて、青の文字列の最大共通接頭辞が緑の文字列に覆われているとき、赤の文字列の所の最大共通接頭辞って青の文字列と一致しますよね。
これを利用すれば結構計算量を省略出来そうですね。
青の文字列が緑の文字列からはみだしている場合はどうでしょう。
この場合は、そのまんま計算結果を再利用することは出来なさそうなので、新たに計算をする必要がありそうです。
ただ、紫の枠で囲った部分は一致しているはずなので、これは利用しましょう。
というアイデアをそのまま実装するとこうなります。
int c = 0; for (int i = 1; i < S.size(); i++){ if (i+A[i-c] < c+A[c]) { A[i] = A[i-c]; } else { int j = max(0, c+A[c]-i); while (i+j < S.size() && S[j] == S[i+j]) ++j; A[i] = j; } } A[0] = S.size();
このコードは実装方針が違うだけで最初に載せたコードとほぼ同じことをしています。
とりあえず正しい答えは計算できそうなのではないでしょうか？
計算量解析はManacherのときと同じようにすれば O(|S|) であることが言えます。
せっかくなので２つ目のコードをベースに解析してみましょう。
int c = 0; for (int i = 1; i < S.size(); i++){ if (i+A[i-c] < c+A[c]) { A[i] = A[i-c]; } else { int j = max(0, c+A[c]-i); while (i+j < S.size() && S[j] == S[i+j]) ++j; A[i] = j; c = i; } }
今回はwhileの中の「++j」が実行される回数が |S| 程度であることを言えば良さそうです。
・f(i) を i+A[i] と定義しておきます。
「int j = max(0, c+A[c]-i);」等に注意すると、各 i での j は
・f(c) - i ≤ j ≤ |S| - i
の範囲に収まります。「A[i] = j;」を踏まえて移項をすると、
・f(c) ≤ f(i) ≤ |S|
新しい f(c) は f(i) になるため、f(c) は ++j された回数だけ毎回増えていきます。f(c) は常に |S| 以下なので、++j の回数も |S| 以下ですね。
図を書いて i+A[i] の位置に注目してみると O(|S|) になることが直感的に分かりやすいのではないかと思います。
なお、この解析はManacherの方でも同様に適用できます。Manacherの記事では少し複雑な解析をしましたが、原理を考えればシンプルな話だったんですね。
以上、Z algorithmでした。
