問題の背景

文字列 s が与えられ、その中にある最長の連続する回文部分文字列の長さを求めたいとします。単純なアプローチとしては、すべての部分文字列を列挙し、それぞれが回文かどうかを判定する方法がありますが、これは O(n^3) の計算量となり非効率です。

より良い方法として、各位置を中心として左右に拡張していく O(n^2) アルゴリズムが考えられます。この方法では、奇数長の回文（中心が文字）と偶数長の回文（中心が文字の間）の両方を扱う必要があります。これを統一的に扱うために、元の文字列の各文字の間にダミー文字（例: #）を挿入することで、すべての回文を奇数長として扱えるように前処理を行います。

Manacherアルゴリズムの概要

Manacher（マラカー）は、回文の対称性を利用することで、線形時間 O(n) で最長回文部分文字列を求めるアルゴリズムです。名前は発案者の名前に由来していますが、「馬車」のようなイメージとは関係ありません。

この手法は、すでに計算済みの回文情報を活用して、現在の位置における回文半径の初期値を高速に決定します。これにより、無駄な比較を大幅に削減できます。

アルゴリズムの詳細

まず、入力文字列 s を変換します。例えば、"abc" は "#a#b#c#" のように変換されます。これにより、すべての回文が奇数長として扱われます。

次に、配列 radius[i] を定義します。これは、変換後の文字列において、位置 i を中心とする最長回文の「半径」（中心から端までの距離）を表します。

アルゴリズムの肝は、既知の回文領域を利用して初期半径を設定することです。具体的には、これまでに見つかった最も右に伸びる回文の範囲 [left, right] を保持します。現在のインデックス i がこの範囲内にある場合、i について、対称の位置 j = left + right - i の半径情報を利用できます。

ただし、j の回文が [left, right] の境界を越える可能性があるため、安全のために次の式で初期半径を設定します：

int init = (i > right) ? 1 : min(radius[mirror], right - i + 1);

ここで mirror = left + right - i です。

この初期値から出発し、可能であればさらに左右に拡張していきます。拡張が完了したら、radius[i] を更新し、必要に応じて left と right も更新します。

計算量の正当性

一見するとネストされたループがあるため O(n^2) のように見えますが、実際には right ポインタが一度進むと戻らないため、全体の比較回数は高々 n 回です。よって、総計算量は O(n) となります。

基本実装

以下は、最長回文部分文字列の長さを求める標準的な実装です。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

int main() {
    string raw;
    cin >> raw;
    
    // 前処理：# を挿入
    string s = "#";
    for (char c : raw) {
        s += c;
        s += '#';
    }
    
    int n = s.size();
    int max_len = 0;
    int radius[n];
    int center = 0, boundary = 0;  // [center - radius[center] + 1, ... , boundary]

    for (int i = 0; i < n; ++i) {
        int mirror = 2 * center - i;
        
        // 初期半径の設定
        if (i < boundary) {
            radius[i] = min(boundary - i, radius[mirror]);
        } else {
            radius[i] = 0;
        }

        // 拡張
        while (i - radius[i] - 1 >= 0 &&
               i + radius[i] + 1 < n &&
               s[i - radius[i] - 1] == s[i + radius[i] + 1]) {
            radius[i]++;
        }

        // 最も右に伸びる回文を更新
        if (i + radius[i] > boundary) {
            center = i;
            boundary = i + radius[i];
        }

        // 実際の回文長（元の文字列における）
        int actual_len = radius[i];  // # を含まない長さは radius[i]
        max_len = max(max_len, actual_len);
    }

    cout << max_len << endl;
    return 0;
}

応用例題

末尾に最短反転を追加（ABC類似問題）

文字列の末尾から始まる最長回文を求めることで、最小の反転接尾辞長を導けます。Manacherで得た radius[i] に対し、i + radius[i] == n を満たすものの中で最大の radius[i] を探せばよいです。

反回文列のカウント（Antisymmetry）

通常の回文は s[i-d] == s[i+d] ですが、反回文は s[i-d] != s[i+d] が必要です。比較条件を変更するだけで対応可能です。また、中心が # の場合のみ有効な場合があるので注意が必要です。結果の集計時には、各 radius[i] が寄与する回文数は radius[i] 個（長さ2, 4, ..., 2*radius[i]）となるため、合計を取ればよいです。

奇数長回文の累乗積（ララ隊）

偶数長回文を無視できるため、前処理で # を挿入せず、通常の文字列上で Manacher を適用します。各中心 i に対して得られる最長奇数長回文の長さは 2 * radius[i] - 1 です。そして、この長さの回文が存在すれば、それより短い奇数長（2 * radius[i] - 3, ...）の回文も必ず存在します。

したがって、長さごとの出現回数をカウントするバケツソートを行い、長い方から順に累積和を取りながら、要求される上位 k 個の長さの積をモジュラー累乗で計算します。