Pythonで2つの文字列の部分列を組み合わせて作れる最長回文の長さを求めるプログラム

問題概要

2つの文字列 s と t が与えられたとき、次の手順で新しい文字列を作ることを考えます。

• s から空でない部分列 sub1 を選びます。
• t から空でない部分列 sub2 を選びます。
• sub1 と sub2 を連結して、新しい文字列を作ります。

この方法で作成できる回文の中で最も長いものの長さを求めてください。もし一つも回文が作れない場合は 0 を返します。

たとえば、s = "hillrace"、t = "cargame" という入力の場合、出力は 7 になります。これは、s から "race" を、t から "car" を取り出して連結すると "racecar" という長さ7の回文が作れるためです。

解法のアプローチ

この問題は区間DP（動的計画法）を用いて効率的に解くことができます。基本的なアイデアは以下の通りです。

• まず、2つの文字列を連結した word = s + t に対して、最長回文部分列（LPS）の長さを DP テーブルに求めておきます。
• ただし、条件として「両方の文字列から必ず1文字以上選ぶ」必要があるため、回文全体が片方の文字列だけに含まれるケースは除外しなければなりません。
• そこで、s[i] と t[j] が一致するペアが少なくとも1つ含まれる場合のみ答えとして採用します。これにより、両方の文字列から文字が使われていることが保証されます。

アルゴリズムの手順

1. n := s の長さ、m := t の長さとします。
2. word := s + t とします。
3. (n+m) × (n+m) のサイズの2次元配列 dp を用意し、すべて 0 で初期化します。
4. i を n+m-1 から 0 まで減らしながら、j を i から n+m-1 まで増やしながら以下を処理します。
   • i == j の場合：dp[i][j] := 1（1文字はそれ自体が長さ1の回文）
   • word[i] == word[j] の場合：dp[i][j] := 2 + dp[i+1][j-1]（両端が一致すれば内側の結果に2を加算）
   • それ以外の場合：dp[i][j] := max(dp[i+1][j], dp[i][j-1])（どちらか一方を縮めた結果の最大値）
5. ans := 0 とします。
6. i を 0 から n-1 まで、j を m-1 から 0 まで減らしながら走査し、s[i] == t[j] が成立するときに ans := max(ans, dp[i][n+j]) と更新します。
7. 最後に ans を返します。

Pythonでの実装例

def solve(s, t):
    n, m = len(s), len(t)
    word = s + t
    dp = [[0] * (n + m) for _ in range(n + m)]

    for i in range(n + m - 1, -1, -1):
        for j in range(i, n + m):
            if i == j:
                dp[i][j] = 1
            elif word[i] == word[j]:
                dp[i][j] = 2 + dp[i + 1][j - 1]
            else:
                dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])

    ans = 0
    for i in range(n):
        for j in range(m - 1, -1, -1):
            if s[i] == t[j]:
                ans = max(ans, dp[i][n + j])
    return ans

s = "hillrace"
t = "cargame"
print(solve(s, t))

入力例

s = "hillrace"
t = "cargame"

出力例

7

計算量について

DPテーブルのサイズは (n+m) × (n+m) であり、各セルの計算は定数時間で行えるため、時間計算量・空間計算量はいずれも O((n+m)²) となります。文字列の長さが数千程度までであれば十分に高速に動作します。