Pythonで最長の回文（パリンドローム）部分文字列の長さを求めるプログラム

文字列 S が与えられたとき、S の中に含まれる最長の回文（パリンドローム）部分文字列の長さを求めることを考えます。ここでは、文字列の長さは最大1000程度であると仮定します。

たとえば、文字列が「BABAC」の場合、最長の回文部分文字列は「BAB」となり、その長さは 3 です。

解法のアプローチ：動的計画法（DP）

この問題は、動的計画法を用いることで効率的に解けます。基本の考え方は、「ある範囲の部分文字列が回文であるかどうか」を小さい部分問題から順に記録していくというものです。

アルゴリズムの手順

1. 文字列の長さと同じサイズの正方行列（2次元配列）dp を定義し、すべて False で初期化します。dp[i][j] は「s[i..j] が回文であるか」を表します。
2. 対角成分を True に設定します。すなわち、すべての i について dp[i][i] = True とします（長さ1の文字列は必ず回文になるため）。
3. start := 0 として開始位置を初期化します。
4. 部分文字列の長さ l を 2 から len(S) まで順に試します。
   • 開始位置 i を 0 から len(S) - l まで動かし、end := i + l とします。
   • l == 2 の場合：s[i] == s[end-1] であれば、dp[i][end-1] = True とし、max_len := l、start := i を更新します。
   • それ以外の場合：s[i] == s[end-1] かつ dp[i+1][end-2] が True であれば、dp[i][end-1] = True とし、max_len := l、start := i を更新します。
5. 最後に max_len を返します。

Pythonでの実装例

class Solution(object):
    def solve(self, s):
        n = len(s)
        # dp[i][j] は s[i..j] が回文かどうかを表す
        dp = [[False for _ in range(n)] for _ in range(n)]

        # 長さ1の部分文字列はすべて回文
        for i in range(n):
            dp[i][i] = True

        max_length = 1
        start = 0

        # 部分文字列の長さ l を2から順に調べる
        for l in range(2, n + 1):
            for i in range(n - l + 1):
                end = i + l
                if l == 2:
                    # 隣接する2文字が一致すれば回文
                    if s[i] == s[end - 1]:
                        dp[i][end - 1] = True
                        max_length = l
                        start = i
                else:
                    # 両端が一致し、内側も回文なら回文
                    if s[i] == s[end - 1] and dp[i + 1][end - 2]:
                        dp[i][end - 1] = True
                        max_length = l
                        start = i
        return max_length

ob = Solution()
print(ob.solve('BABAC'))

入力

BABAC

出力

3

このコードでは、まず長さ1の部分文字列をすべて回文としてマークし、次に長さ2、3、…と順に範囲を広げながら判定していきます。両端の文字が一致し、かつその内側がすでに回文であれば、全体も回文であると判断できるのがポイントです。

なお、入力が「ABBABBC」の場合、最長の回文部分文字列は「BBABB」となるため、出力は 5 になります。

計算量について

このアルゴリズムでは、すべての開始位置と長さの組み合わせを調べるため、時間計算量は O(n²)、DPテーブルを保持するため空間計算量も O(n²) となります。文字列の長さが1000程度であれば、十分に高速に動作します。