Cho hai chuỗi s, t. Tạo chuỗi bằng: chọn subsequence không rỗng sub1 từ s, sub2 từ t, nối sub1+sub2. Tìm độ dài palindrome dài nhất có thể tạo được. Không thể tạo thì trả 0.
Ví dụ: s = "hillrace", t = "cargame" → output = 7 ("race" + "car" = "racecar").
Giải thuật (DP Longest Palindromic Subsequence trên s+t)
- word = s + t. DP[i][j] = độ dài LPS trong word[i..j].
- Khởi tạo DP[i][i] = 1. Điền theo chiều tăng độ dài.
- Duyệt i từ n-1 xuống 0, j từ m-1 xuống 0: nếu s[i] == t[j], ans = max(ans, DP[i][n+j]).
Code 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)) # 7
Đầu vào / Đầu ra
Input: "hillrace", "cargame"
Output: 7