文字列sから最長の回文部分文字列を見つける問題について、Manacherのアルゴリズムはその解法の一つです。このアルゴリズムは1957年にManacherによって考案され、時間計算量が線形O(n)に改善されます。

問題

入力: 文字列 s 出力: s の最長の回文部分文字列

例

例 1:
入力: s = "babad"
出力: "bab" または "aba"

例 2:
入力: s = "cbbd"
出力: "bb"

例 3:
入力: s = "a"
出力: "a"

例 4:
入力: s = "ac"
出力: "a"

Manacherのアルゴリズム

このアルゴリズムは、文字列内の各位置を中心として左右に拡張可能な最大の長さを記録する配列Pを使用します。また、文字列の各文字間に#を挿入し、両端に^と$を追加することで、中心が文字間にある場合も考慮できます。

例えば、Sが変換後の文字列、Pが各位置の拡張可能な長さを表す配列とします。

• P[8] = 3 は、acaという回文が存在することを示します。
• P[11] = 4 は、caacという回文が存在することを示します。

Pの値から元の文字列の回文部分を求めるには、PのインデックスからP[i]を引いて2で割ります。

具体的な実装

以下のコードは、Manacherのアルゴリズムを用いて最長の回文部分文字列を求めるものです。

public String preProcess(String s) {
    int n = s.length();
    if (n == 0) return "^$";
    StringBuilder ret = new StringBuilder("^");
    for (int i = 0; i < n; i++) {
        ret.append("#").append(s.charAt(i));
    }
    ret.append("#$");
    return ret.toString();
}

public String longestPalindrome(String str) {
    String S = preProcess(str);
    int n = S.length();
    int[] P = new int[n];
    int center = 0, right = 0;

    for (int i = 1; i < n - 1; i++) {
        int mirror = 2 * center - i;
        if (right > i) {
            P[i] = Math.min(right - i, P[mirror]);
        } else {
            P[i] = 0;
        }

        while (S.charAt(i + 1 + P[i]) == S.charAt(i - 1 - P[i])) {
            P[i]++;
        }

        if (i + P[i] > right) {
            center = i;
            right = i + P[i];
        }
    }

    int maxLen = 0;
    int centerIndex = 0;
    for (int i = 1; i < n - 1; i++) {
        if (P[i] > maxLen) {
            maxLen = P[i];
            centerIndex = i;
        }
    }
    int start = (centerIndex - maxLen) / 2;
    return str.substring(start, start + maxLen);
}

このアルゴリズムの時間計算量はO(n)であり、空間計算量はO(n)です。これは、大部分の位置で既存の結果と対称性を利用して効率的に計算できるためです。