CSES - Longest Palindrome | Xâu đối xứng dài nhất
Xem PDF
Điểm:
1800 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Cho một xâu, nhiệm vụ của bạn là xác định xâu con đổi xứng dài nhất của xâu. Ví dụ, xâu đối xứng dài nhất trong aybabtu là bab.
Input
- Dòng đầu vào duy nhất chứa một chuỗi độ dài \(n\). Mỗi kí tự là một trong những
a-z.
Output
- In xâu đối xứng dài nhất trong xâu. Nếu có một số đáp án, bạn có thể in bất kỳ đáp án nào trong số đó.
Constraints
- \(1 \leq n \leq 10^6\)
Example
Test 1
Input
aybabtu
Output
bab
Bình luận
mn oi lam v sai cho nao ma no bi memory exceed v:((
def xaudainhat(s):
n = len(s)
dp = [[False] * n for j in range(n)]
start = 0
max_len = 1
for i in range(n):
dp[i][i] = True
for i in range(n-1):
if s[i] == s[i+1]:
dp[i][i+1] = True
start = i
max_len = 2
for a in range(3, n+1):
for i in range(n - a + 1):
j = i + a - 1
if s[i] == s[j] and dp[i+1][j-1]:
dp[i][j] = True
if a > max_len:
start = i
max_len = a
return s[start:start + max_len]
n = input()
kq = xaudainhat(n)
print(kq)
4 bình luận nữa