Pythonで最長の回文部分文字列を求める方法｜動的計画法による解法を徹底解説

文字列 S が与えられたとき、その中に含まれる最長の回文部分文字列を求める問題を考えてみましょう。ここでは文字列 S の長さは最大 1000 であると仮定します。たとえば、文字列が「BABAC」であれば、最長の回文部分文字列は「BAB」となります。

回文とは、前から読んでも後ろから読んでも同じになる文字列のことです。この問題は動的計画法（DP）を用いることで効率的に解くことができます。

動的計画法による解法の手順

この問題を解くために、以下の手順に従います。

• 文字列の長さと同じサイズの正方行列（2次元配列）を定義し、すべて False で初期化する
• 主対角成分を True に設定する。すなわち、0 から（長さ − 1）までのすべての i に対して DP[i][i] = True とする
• start := 0 と初期化する
• 部分文字列の長さ l を 2 から文字列 S の長さまで順にループさせる
  • 開始位置 i を 0 から（文字列の長さ − 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] であれば、DP[i][end - 1] = True、max_len := l、start := i と更新する
• 最後に、インデックス start から start + max_len までの部分文字列を返す

DPテーブルの意味

dp[i][j] は「s[i] から s[j] までの部分文字列が回文であるかどうか」を表します。長さ 1 の部分文字列は常に回文となるため、対角成分は True に設定されます。さらに、より長い部分文字列が回文になる条件は、両端の文字が一致していること、かつその内側の部分文字列も回文であることの2つです。この性質を利用して、短い部分文字列から順に判定を積み上げていくのが、このアルゴリズムの核心となります。

Pythonでの実装例

理解を深めるために、以下の実装例を見てみましょう。

class Solution(object):
    def longestPalindrome(self, s):
        # 文字列の長さ × 長さの2次元DPテーブルを False で初期化
        dp = [[False for i in range(len(s))] for i in range(len(s))]
        # 長さ1の部分文字列は必ず回文なので、対角成分を True に設定
        for i in range(len(s)):
            dp[i][i] = True
        max_length = 1
        start = 0
        # 部分文字列の長さ l を 2 から順番に調べていく
        for l in range(2, len(s)+1):
            for i in range(len(s)-l+1):
                end = i+l
                if l == 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 s[start:start+max_length]

ob1 = Solution()
print(ob1.longestPalindrome("ABBABBC"))

入力

"ABBABBC"

出力

"BBABB"

計算量について

このアルゴリズムでは、すべての開始位置 i と部分文字列の長さ l の組み合わせに対して回文判定を行うため、時間計算量は O(n²) となります。また、DPテーブルを保持する必要があるため、空間計算量も O(n²) です。ただし、文字列の長さが 1000 程度であれば十分に高速に動作するため、実用上は問題ありません。