ปัญหา
สองสตริง s, t เลือก Subsequence sub1 จาก s และ sub2 จาก t ต่อกัน (sub1 + sub2) หา Palindrome ยาวที่สุดได้
ตัวอย่าง
s = "hillrace", t = "cargame" → Output: 7
sub1 = "race" (จาก s), sub2 = "car" (จาก t) → "racecar" (Palindrome, Length 7)
อัลกอริทึม (DP on Concatenated String)
- Concatenate: word = s + t
- DP[i][j] = LPS (Longest Palindromic Subsequence) Length ใน word[i..j]
- Standard LPS DP: ถ้า word[i]==word[j] → 2+DP[i+1][j-1] Else Max(DP[i+1][j], DP[i][j-1])
- คำตอบ: Max ของ DP[i][n+j] สำหรับทุก i,j ที่ s[i] == t[j] (จุดเชื่อมระหว่าง s และ t)
ตัวอย่างโค้ด
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ความซับซ้อน
- Time: O((n+m)²)
- Space: O((n+m)²)
n,m ≤ 1000 ใช้ได้ (10⁶ Operations)
