回文検出(Manacher)

何を解きたいか

ご存じのように回文とは,のような逆順でも変化しない文字列のことです。このとき、ある文字列の部分文字列で作られる回文の最大長さや数を問う問題を解きたい場合を考えます。ナイーブに解こうとすると二重のfor文で全ての部分文字列を生成し、をチェックすればよいですが、となるので短い文字列にしか適用できません。

この問題を回文の特性を上手に利用してで解く方法があり、それが今回説明するManacherのアルゴリズムです。

どう解くか

上述したように回文の特性を上手いこと利用します。 説明を簡単にするために奇数長の回文のみを検出対象とします。偶数への拡張は別途最後にコード例を示します。

今回は、具体例としてという文字列で考えます。

この文字列を頭から見ていって、各文字を中心に両端に何文字同じ文字を持つかをメモしていきます。これは、メモされた値をとすると、その文字を中心にの長さの回文があるという情報をメモしたことになります。

具体的に図で見ていくと次のような形で処理が進んでいきます。

◆STEP1
1文字目はで、右側にしか文字が存在せず回文の長さは自分自身だけのため、1をメモします。

◆STEP2
2文字目はで、両側にが存在するため、回文の長さは自分自身＋1として2をメモします。

◆STEP3
3文字目はで、両側には同じ文字は存在しないため、1をメモします。

◆STEP4
4文字目はで、両側は矢印のの部分まで同じ文字が続くので、4をメモします。

　この先STEP5,6と進めていきたいところですが、文字列をよく見るとSTEP4でを中心にという回文が構成されていることが分かっているため、STEP5,6の結果はSTEP2,3と同じになり探索不要なことが分かります。

◆STEP5,6

このように、ある位置で長さの回文が検出されたときまでの計算結果を用いることで探索を効率化しようというのが基本アイデアです。
ただここで、利用できる過去の計算結果の範囲には気を付ける必要があります。
例えばSTEP7ではわかりやすくそういったことが起きます。

◆STEP7
このSTEPのメモ値は3となり、着目文字の対称にある左端ののメモ値とは一致しません。

ある文字を中心に一文字ずつ両側に同じ文字があるかどうかを探索していくとき、現在着目してる文字を含む最長の回文(STEP7では)より内側までしか対称性が保証されません。そのため、最長の回文より外の範囲へ探索範囲が伸びた時点でそこから先は未知の世界のため、真面目に探索する必要があります。

実装例

これらを実装したコード例を下記に示します。

#include <bits/stdc++.h>
using namespace std;

int main() {
  string s = "abacababa";
  int n = s.size();

  vector<int> rad(n);
  int c = 0, r = 0;
  
  while (c < n) {
    // cを中心に同じ文字がどこまで連続するか
    while (0 <= c - r && c + r < n && s[c - r] == s[c + r]) r++;
    rad[c] = r;

    //回文の長さに応じて利用可能な範囲を確認しつつメモ
    int k = 1;
    while (0 <= c - k && k + rad[c - k] < r) {
      rad[c + k] = rad[c - k];
      k++;
    }
    //すでに計算が終わった分だけ中心と探索半径をずらす
    c += k;
    r -= k;
  }
  
  int Lmax = *max_element(rad.begin(), rad.end()) * 2 - 1;
  cout << Lmax << endl;
  return 0;
}

偶数長への拡張

偶数長回文への拡張は簡単で、元の文字列の各文字の間にを挟んで同じアルゴリズムで検出すればよいです。そうするとのインデックスには偶数長の回文の長さが、元の文字のインデックスには奇数長の回文の情報がメモされます。
ただし、最後に分の長さを差し引きしなければならないことに注意が必要です。

#include <bits/stdc++.h>
using namespace std;

int main() {
  string _s = "abacabaaa";
  int n = _s.size();
  //'#'の追加
  string s(2 * n + 1, '#');
  for (int i = 0; i < n; i++) s[2 * i + 1] = _s[i];
  n = 2 * n + 1;

  vector<int> rad(n);
  int c = 0, r = 0;

  while (c < n) {
    // cを中心に同じ文字がどこまで連続するか
    while (0 <= c - r && c + r < n && s[c - r] == s[c + r]) r++;
    rad[c] = r;

    //回文の長さに応じて利用可能な範囲を確認しつつメモ
    int k = 1;
    while (0 <= c - k && k + rad[c - k] < r) {
      rad[c + k] = rad[c - k];
      k++;
    }
    //すでに計算が終わった分だけ中心と探索半径をずらす
    c += k;
    r -= k;
  }
  //'＃'分の補正
  for (int i = 0; i < n; i++) {
    if (i % 2 == 0)
      rad[i] = (rad[i] - 1) / 2;
    else
      rad[i] /= 2;
  }

  int Lmax = *max_element(rad.begin(), rad.end()) * 2 - 1;
  cout << Lmax << endl;
  return 0;
}

参考

以下、参考にさせて頂いたサイトです。
snuke.hatenablog.com

よくある理由で、

はじめました。
競プロやったり、自作キーボード組んだりするのが好きです。

一応今年中にAtCoderで水色到達を当面の目標にしてるんですが、アルゴリズムの勉強とかしたそばから忘れていくので、記憶定着目的でいろいろ書いてく。