最長回文部分文字列の見つけ方をやさしく解説

「回文（かいぶん）」とは、前から読んでも後ろから読んでも同じ文字列のことです。たとえば「level」や「noon」は回文になっています。

今回は、文字列の中に含まれる「最も長い回文の部分文字列」を見つける方法について、やさしく解説します。

はるか

回文―左右対称、好き。長さ勝負しよう。

ふゅか

いいね！まずはどうやって最長を探すか考えよっか。

1. 問題

文字列 s が与えられたとき、その中に含まれる 最長の回文部分文字列 を返す。

1.1. 例1

• 入力: "abacdfgdcaba"
• 出力: "aba"

1.2. 例2

• 入力: "aabcdcb"
• 出力: "bcdcb"

2. アイデア：「中心から広げる」

回文は「左右対称」の構造を持っています。そこで、文字列の中の各位置を“中心”と見なして、そこから左右に広げて回文になっているかを調べる方法が有効です。

この方法は英語のアルゴリズムのサイトとかでは「Center Expansion Method」とも呼ばれています。

2.1. 回文には2つのタイプがあります

• 奇数長の回文 → 1文字を中心に左右対称（例: "racecar" の e）
• 偶数長の回文 → 2文字の間を中心に左右対称（例: "noon" の oo）

はるか

奇数…文字１つ中心。偶数…隙間中心。

ふゅか

「racecar」は奇数、「noon」は偶数ね！区別して両方試すと抜け漏れゼロ。

3. 解法のステップ

1. 文字列の全ての位置を「中心候補」として見る（1文字または2文字の隙間）
2. 左右に文字を広げて、回文かどうかをチェック
3. 最長の回文が見つかったら記録しておく
4. 全ての中心候補を試し終えたら、記録された範囲を返す

4.  コード全体

def expand(left, right, s):
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    return left + 1, right - 1

s = "aabcdcb"

best_cfg = (0, 0)
best_length = 0

for i in range(len(s)):
    l_odd, r_odd = expand(i, i, s)
    length_odd = r_odd - l_odd + 1

    l_even, r_even = expand(i, i + 1, s)
    length_even = r_even - l_even + 1

    if length_odd > best_length:
        best_cfg = (l_odd, r_odd)
        best_length = length_odd

    if length_even > best_length:
        best_cfg = (l_even, r_even)
        best_length = length_even

print("最長回文の位置:", best_cfg)
print("最長回文部分文字列:", s[best_cfg[0] : best_cfg[1] + 1])

5. コードのポイント

5.1. expand のポイント

• この関数は、指定された left と right を中心として、回文が成立する限り左右に広げていきます。
• ループを抜けた時点では、1文字外にはみ出しているため、left + 1, right - 1 で調整して戻しています。

def expand(left, right, s):
    # 回文であるかぎり、左右に1文字ずつ拡張していく
    while left >= 0 and right < len(s) and s[left] == s[right]:
        left -= 1
        right += 1
    # 最後に一歩余計に進んでいるので、1文字ずつ戻す
    return left + 1, right - 1

5.2. 記録

s = "aabcdcb"

best_cfg = (0, 0)       # 回文の開始位置と終了位置を記録
best_length = 0         # 現時点での最長回文の長さ

• best_cfg は最長回文の「開始・終了位置」のタプルです。
• best_length はその長さを記録しておきます。

6. 実行例

s=aabcdcbであるとき、

7. もっと速くしたい人へ

もし文字列がもっと長くて処理を速くしたい場合は、「Manacher法」というアルゴリズムを使うと O(n) で解けます。

8. まとめ

• 回文の特徴＝「左右対称」を活かす
• すべての位置を中心として試し、左右に広げて確認する
• 実装がシンプルで、実用にも強い方法