問題の定義

与えられた文字列から、連続する部分文字列の中で最も長い回文（前後どちらから読んでも同じになる文字列）を求める問題を「最長回文部分文字列問題」と呼ぶ。例えば文字列 "aaaba" では、"aaa" や "aba" が回文であり、その中で最長のものは "aaa" となる。

この問題は動的計画法でも解けるが、時間計算量が O(n²) となる。それに対して Manacher アルゴリズム（マラカー法）は O(n) の線形時間で解決できるため、非常に効率的である。

アルゴリズムの基本的な発想

Manacher アルゴリズムの核心は、「回文の対称性」を活用して重複した計算を避ける点にある。ある位置を中心とする回文が存在する場合、その内部にある別の回文は、中心に対して対称な位置に類似の構造を持つ可能性がある。

具体的には、現在までに見つかった最も右側に広がる回文の範囲（右端 right_edge）内にあるインデックスについては、過去に計算済みの対称位置の情報を元に初期半径を設定できる。これにより、無駄な比較を大幅に削減できる。

文字列の前処理と偶奇統一

偶数長の回文（例: "abba"）は明確な中心文字を持たないため、すべての文字の間にダミー文字（例: '#'）を挿入して、すべての回文が明確な中心を持つようにする。

たとえば、"aba" → "#a#b#a#"、"abba" → "#a#b#b#a#" と変換される。この変換により、奇数・偶数の両方の回文を統一的に扱えるようになる。

アルゴリズムの実装

以下に Python を用いた Manacher アルゴリズムの実装を示す。このコードは最長回文の長さだけでなく、その内容と出現回数も同時に抽出する。

def find_longest_palindromes(s):
    if not s:
        return 0, [], 0

    # ダミー文字 '#' を挿入して偶奇を統一
    transformed = '#'.join('^{}$'.format(s))
    length = len(transformed)
    
    # 各位置を中心とする回文の半径を格納
    radius = [0] * length
    center = right_edge = 0  # 現在最も右まで広がった回文の中心と右端
    max_len = 0
    palindromes = []

    for i in range(1, length - 1):
        # 対称性を利用して初期半径を設定
        if i < right_edge:
            mirror = 2 * center - i
            radius[i] = min(right_edge - i, radius[mirror])
        
        # 半径を現在の値からさらに拡張
        left = i - (radius[i] + 1)
        right = i + (radius[i] + 1)
        while transformed[left] == transformed[right]:
            radius[i] += 1
            left -= 1
            right += 1
        
        # 右端を超えた場合は center と right_edge を更新
        if i + radius[i] > right_edge:
            center = i
            right_edge = i + radius[i]
        
        # 最長回文の更新
        actual_length = radius[i]
        if actual_length > max_len:
            max_len = actual_length
            palindromes = [transformed[i - radius[i]:i + radius[i] + 1].replace('#', '')]
        elif actual_length == max_len and actual_length > 0:
            candidate = transformed[i - radius[i]:i + radius[i] + 1].replace('#', '')
            if candidate not in palindromes:  # 重複除外
                palindromes.append(candidate)

    count = len(palindromes)
    return max_len, palindromes, count

# 使用例
input_str = "aaaba"
length, subs, num = find_longest_palindromes(input_str)
print("最長回文部分文字列の長さ:", length)
print("最長回文部分文字列:", subs)
print("種類数:", num)

出力結果

最長回文部分文字列の長さ: 3
最長回文部分文字列: ['aaa']
種類数: 1

動作のポイント

• 対称性の利用: 現在の右端 right_edge 内にあるインデックスは、対称位置の情報を元に初期半径を割り当てられる。
• 境界の更新: 拡張後の回文がこれまでの右端を超えたら、center と right_edge を更新。
• 線形時間: 各文字について右端を越える操作は全体で高々 n 回しか発生しないため、O(n) で完了する。

まとめ

Manacher アルゴリズムは、回文固有の対称性を巧みに利用することで、最長回文部分文字列を線形時間で求めることができる強力な手法である。前処理による偶奇統一と、既知の情報を活用する戦略が、計算効率の向上に大きく寄与している。