Python의 하위 시퀀스에서 최대 회문 길이를 찾는 프로그램

<시간/>

두 개의 문자열 s와 t가 있다고 가정합니다. 우리는 다음과 같은 방식으로 문자열을 만들고 싶습니다 -

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]
      의 최대값
답변 :=0
범위 0에서 n - 1에 있는 i에 대해 수행
- m - 1 ~ -1 범위의 j에 대해 1 감소, 수행
  - s[i]가 t[j]와 같으면
    - ans =ans 및 dp[i, n + j]
      의 최대값
반환

예시

이해를 돕기 위해 다음 구현을 살펴보겠습니다.

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