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

昨日の記事の続きです。

Manacher

文字列が与えられた時、各 i について「文字 i を中心とする最長の回文の半径」を記録した配列 R を O(|S|) で構築するアルゴリズムです。半径というのは、(全長+1)/2です。
例えば、

abaaababa
121412321

こんな感じです。

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

int i = 0, j = 0;
while (i < S.size()) {
  while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
  R[i] = j;
  int k = 1;
  while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
  i += k; j -= k;
}

このコードが何をしているのかを見ていきます。
とりあえず、i は現在の更新箇所で、j はそのときの半径です。
while内の１行目のwhileは、愚直に「文字 i を中心とする最長の回文の半径」を計算しているようです。
求めた答えを R[i] = j で代入して、
int k = 1、while(なんたら)かんたら、i+=k,j-=k・・・？？？？？？？？
この辺りがよく分かりませんねぇ。
恐らく、ベースとなるアイデアを見てみた方が良さそうです。

ベースとなるアイデアについて見てみましょう。
キーワードは「既に計算したものを利用する」です。

黄色の文字を中心とした回文（長いので以降は黄回文みたいに呼ぶことにします）があって、黄色の文字を挟んで対称な位置に青の文字と赤の文字があるときを考えます。
青回文が黄回文に完全に覆われている場合、対称性を考えると赤回文の最長半径は青回文と一致しますよね。

こういう風に黄色の文字をまたいでいる場合でも大丈夫です。
これを利用すれば結構計算量を省略出来そうですね。

青回文が黄回文からはみだしている場合はどうでしょう。

この場合は、そのまんま計算結果を再利用することは出来なさそうなので、新たに計算をする必要がありそうです。
ただ、紫の枠で囲った部分は回文になっているはずなので、これは利用しましょう。

というアイデアをそのまま実装するとこうなります。

int c = 0;
for (int i = 0; i < S.size(); ++i) {
  int l = c - (i-c);
  if (i+R[l] < c+R[c]) {
    R[i] = R[l];
  } else {
    int j = c+R[c] - i;
    while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
    R[i] = j;
    c = i;
  }
}

このコードは実装方針が違うだけで最初に載せたコードとほぼ同じことをしています。
とりあえず正しい答えは計算できそうなのではないでしょうか？

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

while (i < S.size()) {
  while (i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) ++j;
  R[i] = j;
  int k = 1;
  while (i-k >= 0 && k+R[i-k] < j) R[i+k] = R[i-k], ++k;
  i += k; j -= k;
}

一見２重ループなのでO(|S|^2)っぽく見えますね。
今回は少し複雑です。i,j,kに注目して解析しましょう。関係のありそうな部分を取り出してみます。
・W：while(i-j >= 0 && i+j < S.size() && S[i-j] == S[i+j]) の中の「++j;」
・X：while(i-k >= 0 && k+R[i-k] < j) の中の「++k;」
・Y：i += k;
・Z：j -= k;
で、条件を書き出してみます。
・A：YとZをまとめて考えると、この部分では「i+j」は変化しません。
・B：「i+j」 は |S| 以下です。（位置＋半径なので）
・C：「i+j」 が変化するのは W の部分だけです。
・D：i は各ステップの k の和、つまり X を回した回数の合計と一致します。
・E：明らかに i は常に |S| 以下です。
A~C より、W のwhileを回す回数が合計で |S| 回程度であることが言えます。
D,E より、X のwhileを回す回数も合計で |S| 回程度であることが言えます。
というわけで、うまいこと計算量O(|S|)になってるんですよねー。すごい。

ちなみに、普通のManacherをやると奇数長の回文しか検出できませんが、「a$b$a$a$b」みたいにダミー文字を間に挟むと偶数長のものも検出できるようにできます。

以上、Manacherでした。

前の記事（KMP） | 次の記事（Z algorithm）