CSES - Longest Palindrome | Xâu đối xứng dài nhất

Tác giả:

Dạng bài

Đ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

0

thuannguyen1972dn 6:17 p.m. 3 Tháng 5, 2024

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)

include<bits/stdc++.h>

using namespace std;

define ll long long

ll a[1000][1000];

int main() {
string s;
cin >> s;
ll ans = 0;
ll y = 0, p = 0;

for (ll len = 2; len <= s.size(); len++) {
    for (ll i = 0; i < s.size() - len + 1; i++) {
        ll j = i + len - 1;

        if (len == 2 || len == 3) {
            if(s[i]==s[j]) a[i][j]=1;
        } else {
            if(s[i] == s[j] && a[i + 1][j - 1] == 1) a[i][j]=1;
        }

        if (j - i + 1 > ans && a[i][j] == 1) {
            y = i;
            p = j;
            ans = j - i + 1;
        }
    }
}

cout << s.substr(y, ans);

return 0;

}
em dùng qhđ bị runtime error , ai cíu em với :(. cảm ơn mng ạ

2

mt_chain 9:53 p.m. 17 Tháng 5, 2023

Hash + two pointer có AC k nhỉ

1 phản hồi

0

hungnt 4:29 p.m. 28 Tháng 11, 2022 ← đã chỉnh sửa →

Bài này mình làm bằng hash không hiểu sao sai mất 1 test

0

dang7rickroll 3:26 p.m. 18 Tháng 9, 2022 ← đã chỉnh sửa →

**Hint**
$Manacher's$ $Algorithm$

1 phản hồi