Palindrome dài nhất

Điểm: 0,29 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Nguồn bài:

Nguyễn Hoành Tiến

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho xâu ~S~.

Tìm độ dài của xâu con (liên tiếp) đối xứng dài nhất.

Input

Dòng ~1~: Số nguyên dương ~N \leq 5 \times 10^4~.

Dòng ~2~: Xâu ký tự độ dài ~N~.

Output

1 dòng duy nhất gồm độ dài của xâu con đối xứng dài nhất.

Sample Input

5
abacd

Sample Output

Bình luận

Hãy đọc nội quy trước khi bình luận.

-2

hoangquys đã bình luận lúc 7, Tháng 1, 2026, 14:47

Bài này O(N^2) vẫn AC nhé, solution khác là có thể dùng sliding window để làm bài này

0
dotuankiet18072008 đã bình luận lúc 1, Tháng 1, 2026, 0:52 ← sửa 2 →
* Mình xin góp 1 ý tưởng cho những bài chưa nghĩ ra cách full ạ*

Ta sẽ chia bài toán thành 2 trường hợp đó là xâu đối xứng CHẴN và xâu đối xứng LẺ

Đông thời ta có một số nhận xét về xâu đối xứng như : nếu xâu đối xứng có độ dài L thì có thể không có xâu đối xứng L+2 tuy nhiên nếu ta có xâu đối xứng L + 2 thì chắc chắn việc ta có xâu đối xứng độ dài L

Ta xoáy sâu vào đó để đưa ra cách tìm kiếm nhị phân

* TH1 :xâu độ dài lẻ* ta xây dựng 1 vector để lưu các độ dài lẻ mà xâu S có thể xảy ra ví dụ như test đề bài abacd (5) thì mảng a[] = {1, 3, 5} rồi ta bắt đầu chặt nhị phân l = 0, r = a.size() - 1; và mid = (l+r)/2 sau đó kiểm tra ok(a[mid]) rồi cập nhật các giá trị để thực hiện chặt

ok[a[mid]] kiểm tra xem xâu s có xâu đối xứng nào có độ dài a[mid] ko

* TH2 xâu độ dài chẵn* ta là tương tự như TH1 nhưng mảng lưu trữu độ dài chẵn có thể xảy ra và làm tương tự như TH1 ạ

*Và mình có 1 số lưu ý cho các bạn về 1 số TH bị RTE : *

nên khai báo các biến như int n; string s.... ở ngoài hàm int main() ạ bởi nếu khai báo ở trong có thể bị RTE test cuối ạ

Cảm Ơn mọi người đã tham khảo ạ. Còn code mình xin phép ko gửi ạ bởi mình mong những bạn tham khảo ý tưởng của mình nếu có hứng thú thì có thể tự code mà không bị phụ thuộc vào bên ngoài ạ

-3

vominhmanh10 đã bình luận lúc 9, Tháng 11, 2025, 3:43

xâu đối xứng dùng manacher

import sys
input = sys.stdin.readline

def palin():
    l = 0
    r = -1
    for i in range(n):
        if i <= r: odd[i] = min(r - i, odd[l + r - i])
        while i - odd[i] - 1 >= 0 and i + odd[i] + 1 < n and s[i - odd[i] - 1] == s[i + odd[i] + 1]:
            odd[i] += 1
        if i + odd[i] > r:
            l, r = i - odd[i], i + odd[i]
    l, r = 0, -1
    for i in range(n - 1):
        j = i + 1
        if j <= r: even[i] = min(r - i, even[l + r - j])
        while i - even[i] >= 0 and j + even[i] < n and s[i - even[i]] == s[j + even[i]]:
            even[i] += 1
        if i + even[i] > r:
            l, r = j - even[i], i + even[i]
    return max(max(odd) * 2 + 1, max(even) * 2)


n = int(input())
s = input().strip()
odd = [0] * n
even = [0] * n
print(palin())

2

luuthanhdatbienhoak66 đã bình luận lúc 11, Tháng 9, 2025, 14:04

=))

https://ideone.com/wBFzlC

-3
Hugcodega đã bình luận lúc 17, Tháng 6, 2025, 13:44 ← chỉnh sửa →
Hash + chặt nhị phân là ac

-42

tandochuyentin2022 đã bình luận lúc 19, Tháng 2, 2025, 13:46

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

3

HeroMinhSteve đã bình luận lúc 27, Tháng 1, 2025, 15:28

Gợi ý

Cài MANACHER là ra

-7
phanthien10r đã bình luận lúc 3, Tháng 9, 2024, 17:27
include<bits/stdc++.h>

define ll long long

using namespace std;

const ll maxn = 1e6+7; const ll mod = 1e9+7; const ll base = 26; ll i,j,n,kq,l,r,mid; bool c1,c2; string s;

static ll hl[maxn],hr[maxn],Pow[maxn];

void Hash( ll n ) { hl[0]=0; hr[n+1]=0; Pow[0]=1; for(i=1;i<=n;i++) { hl[i] = ( hl[i-1] * base + s[i] - 'a' ) % mod; Pow[i] = ( Pow[i-1] * base ) % mod; } for(i=n;i>=1;i--) hr[i] = ( hr[i+1] * base + s[i] - 'a' ) % mod; }

bool gethash(ll i, ll j) { ll r1 = ( hl[j] - hl[i-1] * Pow[j-i+1] + modmod ) % mod; ll r2 = ( hr[i] - hr[j+1] * Pow[j-i+1] + modmod ) % mod; if ( r1 == r2 ) return true; else return false; }

int main() { iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0);

cin >> n >> s; s = ' '+s; Hash(n); l = 1; r = n; kq = 1; while ( l<=r ) { mid = (l+r)/2; c1 = false; c2 = false; for(i=1;i<=n-mid+1;i++) if ( gethash(i,i+mid-1) ) { kq = mid; l = mid + 1; c1 = true; break; } if ( c1 == false ) { for(i=1;i<=n-mid;i++) if ( gethash(i,i+mid) ) { kq = mid + 1; l = mid + 2; c2 = true; break; } } if ( c1 == false && c2 == false ) { r = mid - 1; } } cout << kq;

} code ne
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-1

winky đã bình luận lúc 2, Tháng 9, 2024, 8:11

bài này có ver2 không ạ em code O(n^2) vẫn AC ;-;

5

dienthan901 đã bình luận lúc 17, Tháng 2, 2025, 14:52

chắc test yếu, ô cứ đắp 10^6 chữ a là ok (")>

-1

dienthan901 đã bình luận lúc 17, Tháng 2, 2025, 14:52

chắc test yếu, ô cứ đắp 10^6 chữ a là ok (")>

-13
DongDuc08 đã bình luận lúc 20, Tháng 8, 2024, 8:53
Mình bị sai case 3 :( ae nào rảnh giúp với

include<bits/stdc++.h>

using namespace std;

define pb push_back

define N 1000005

define el '\n'

define fo(i,a,b) for(int i=(a);i<=(b);i++)

define pi pair<int,int>

define fi first

define se second

define M 1000

define ll long long

const int mod = 1e9 + 7; const int base = 31; string s; ll hs[N],ht[N],Pow[M]; int n; ll gethashs(int l,int r) { return ((hs[r] - hs[l-1] * Pow[r-l+1])%mod + mod) % mod; } ll gethasht(int l,int r) { return ((ht[r] - ht[l-1] * Pow[r-l+1])%mod + mod) % mod; } void tt() { iosbase::syncwith_stdio(0);cin.tie(NULL);cout.tie(NULL); freopen("paliny.inp","r",stdin); freopen("paliny.out","w",stdout); }

bool ktchan(int n,int mid) { int k = mid *2; fo(i,1,n - k + 1) { if(gethashs(i,i + k - 1) == gethasht(n - i -k + 2,n - i + 1)) return 1; } return 0; } bool ktle(int n,int mid) { int k = mid *2 + 1; fo(i,1,n - k + 1) { if(gethashs(i,i + k - 1) == gethasht(n - i -k + 2,n - i + 1)) return 1; } return 0; }

int le(int n) { int l = 1,r = n /2; int ans = 0; while(l <= r) {int mid = (l + r)/2; if(ktle(n,mid) == 1) {ans = 2mid + 1;l = mid + 1;} else r = mid - 1; } return ans; } int chan(int n) { int l = 1,r = n /2; int ans = 0; while(l <= r) {int mid = (l + r)/2; if(ktchan(n,mid) == 1) {ans = 2mid;l = mid + 1;} else r = mid - 1; } return ans; }

void build_hash() { Pow[0] = 1; fo(i,1,n) Pow[i] = Pow[i-1]*base %mod; fo(i,1,n) hs[i] = (hs[i-1] *base + s[i-1] )% mod; string t = s; reverse(t.begin(),t.end());

fo(i,1,n) ht[i] = (ht[i-1] *base + t[i-1])% mod;

cout << max(chan(n) , le(n)); } int main() { cin >> n >>s; build_hash(); }
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-10
Huy_inIT đã bình luận lúc 24, Tháng 7, 2024, 3:07
hash + chặt nhị phân

vector<ll> POW(1000001);
vector<ll> HASHS(1000001); vector<ll> HASHT(1000001);

ll Get(ll l, ll r) { return ((HASHS[r] - HASHS[l-1] * POW[r - l + 1] % mod) + mod) % mod; }

ll TAKE(ll l, ll r) { return ((HASHT[r] - HASHT[l-1] * POW[r - l + 1] % mod) + mod) % mod; }

bool good(int m, int szt) { for(int i=1; i + m - 1 <= szt; i++) { if(Get(i, i + m - 1) == TAKE(szt - (i + m - 1) + 1, szt - i + 1)) { return true; } } return false; }

TRYHARD main() { #ifndef ONLINEJUDGE #endif fastbuild int n; cin >> n;

string s; cin >> s; string t; t = s; reverse(all(t)); s = ' ' + s; t = ' ' + t; POW[0] = 1; for(int i=1; i<=POW.size(); i++) { POW[i] = (POW[i-1]*256)%mod; } HASH_S[0] = 0; for(int i=1; i<s.size(); i++) { HASH_S[i] = (HASH_S[i-1]*1ll*256 + (int)(s[i]-'a')) % mod; } HASH_T[0] = 0; for(int i=1; i<t.size(); i++) { HASH_T[i] = (HASH_T[i-1]*1ll*256 + (int)(t[i]-'a')) % mod; } int l = 1, r = n , ans = 0; while(l <= r){ int m = (l + r)/2; if(good(m , n)){ l = m + 1; ans = m; } else if(good(m + 1, n)){ l = m + 2; ans = m + 1; } else r = m - 1; } cout << ans; return 0;

}
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-3

pndhpndh đã bình luận lúc 16, Tháng 6, 2024, 3:43

hihi

-7

chunguyen2k8 đã bình luận lúc 14, Tháng 5, 2024, 12:18

HiHi , dùng manacher đi cho ngầu

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

giga_hedgehog đã bình luận lúc 15, Tháng 5, 2024, 0:49

ac

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

vantien1526 đã bình luận lúc 31, Tháng 8, 2023, 15:25

ai đó thông não giúp mình đoạn cnp với ạ :((

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

1

normankr07 đã bình luận lúc 3, Tháng 9, 2023, 4:23

Tại hàm độ dài max không đơn điệu ý bạn, phải cnp các độ dài chẵn riêng và lẻ riêng Bài này bạn có thể làm bằng manacher, mình thấy dễ hơn, tài liệu thì ở đây: https://vnoi.info/wiki/algo/string/manacher.md

1

niahauma đã bình luận lúc 15, Tháng 5, 2023, 11:01

cho mình hỏi tại sao phải chặt nhị phân chẳn lẻ thế ạ

-8

quocdev2009 đã bình luận lúc 14, Tháng 5, 2024, 7:29

include <bits/stdc++.h>

using namespace std;

const int maxn = 5e4, base = 31, MOD = 1e9+7;

int n, hashx[maxn+1], hashn[maxn+1], p[maxn+1]; string s;

int getHashX(int l, int r) { return (hashx[r] - 1llhashx[l-1]p[r-l+1] + 1llMODMOD)%MOD; }

int getHashN(int l, int r) { return (hashn[n - l + 1] - 1llhashn[n - r]p[r - l + 1] + 1llMODMOD)%MOD; }

bool check_distance(int length) { for (int i = 1; i <= n - length + 1; i++) { if (getHashX(i, i + length - 1) == getHashN(i, i + length - 1)) return true; } return false; }

int bs(int l, int r) { int ans = 1; while (l <= r) { int m = (l+r)/2; bool check = false; if (checkdistance(2*m)) { ans = max(ans, 2*m); l = m + 1; check = true; } if (checkdistance(2m+1)) { ans = max(ans, 2m+1); l = m + 1; check = true; } if (!check) r = m - 1; } return ans; }

int main() { iosbase::syncwith_stdio(0); cin.tie(0); cout.tie(0); cin >> n; cin.ignore(); getline(cin, s); s = ' ' + s; p[0] = 1, hashx[0] = 0, hashn[0] = 0; for (int i = 1; i <= maxn; i++) p[i] = 1llp[i-1]base%MOD; for (int i = 1; i <= n; i++) { hashx[i] = (1llhashx[i-1]base + s[i] - 'a' + 1)%MOD; hashn[i] = (1llhashn[i-1]base + s[n-i+1] - 'a' + 1)%MOD; } cout << bs(1, n/2); }

không cần chia ra vẫn AC nhé :>>>

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-5

Vinhzn08 đã bình luận lúc 5, Tháng 7, 2024, 17:10

orz

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-6

y đã bình luận lúc 15, Tháng 5, 2023, 11:45

https://discord.com/channels/660930260405190688/1107185065370337320/1107269792672534569

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-3

YOASOBI đã bình luận lúc 3, Tháng 2, 2023, 1:37

Hash base 31 AC được nè :V

-4

mt1234 đã bình luận lúc 18, Tháng 5, 2023, 5:50

Code kiểu j v :>>

-7

dasher đã bình luận lúc 27, Tháng 1, 2023, 16:53

sao code mình có đpt O(n.n) mà vẫn AC vậy admin

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-10

tboros2 đã bình luận lúc 31, Tháng 12, 2022, 12:26

Bai nay hash ko on lam ;-;

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-2

OrzSeaPosjtive đã bình luận lúc 31, Tháng 12, 2022, 12:43

Tại sao lại k nhỉ

-11

nguyenhainam1012cg đã bình luận lúc 18, Tháng 3, 2023, 15:42

tại nó sai =))))

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

-28

kh0i đã bình luận lúc 20, Tháng 6, 2022, 6:19 ← chỉnh sửa →

[deleted]

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.

61

darkkcyan đã bình luận lúc 3, Tháng 11, 2021, 21:31

Cảm ơn bạn PPAP_1264589 đã đóng góp 3 test khá mạnh cho bộ test của bài này <3. Mình đã rejudge lại toàn bộ submission AC và lần này không chỉ có một vài mà lên đến khoảng 70 submissions đã mất AC :(.