Pythonのサブシーケンスから最大の回文長を見つけるプログラム

sとtの2つの文字列があるとします。次のように文字列を作りたい-

• sから空でないサブシーケンスsub1を選択します。

• tから空でないサブシーケンスsub2を選択します。

• sub1とsub2を連結して、文字列を作成します。

説明されている方法で形成できる最長の回文の長さを見つける必要があります。回文を作成できない場合は、0を返します。

したがって、入力がs ="hillrace" t ="cargame"の場合、sから "race"、rから "car"を取得できるため、出力は7になります。したがって、"racecar"は長さ7の回文です。 。

これを解決するには、次の手順に従います-

• n：=sのサイズ、m：=tのサイズ

• 単語：=s + t

• dp：=サイズ（n + m）x（n + m）の2D配列を作成し、0で埋めます

• （n + m-1）から0の範囲のiの場合、1ずつ減少します。

  • iからn+m-1の範囲のjの場合、実行

    • iがjと同じ場合、

      • dp [i、j]：=1

    • それ以外の場合、word[i]がword[j]と同じである場合、

      • dp [i、j]：=2 + dp [i + 1、j-1]

    • それ以外の場合

      • dp [i、j] =dp [i + 1、j]およびdp [i、j-1]の最大値

• ans：=0

• 0からn-1の範囲のiの場合、実行

  • m-1から-1の範囲のjの場合、1ずつ減少します

    • s[i]がt[j]と同じ場合、

      • ans =ansとdp[i、n + j]

        の最大値

• ansを返す

例

理解を深めるために、次の実装を見てみましょう

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))

入力

[[2,2],[1,2],[3,2]], [[3,1],[3,3],[5,2]]

出力

7