Palindrome dài nhất

Points: 0.29 (partial)

Time limit: 1.0s

Memory limit: 256M

Input: stdin

Output: stdout

Problem source:

Nguyễn Hoành Tiến

Problem types

Allowed languages

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

Comments

Comments

Please read the guidelines before commenting.

-2

hoangquys commented on Jan. 7, 2026, 2:47 p.m.

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

3
dotuankiet18072008 commented on Jan. 1, 2026, 12:52 a.m. ← edit 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 commented on Nov. 9, 2025, 3:43 a.m.

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 commented on Sept. 11, 2025, 2:04 p.m.

=))

https://ideone.com/wBFzlC

-3
Hugcodega commented on June 17, 2025, 1:44 p.m. ← edited →
Hash + chặt nhị phân là ac

-42

tandochuyentin2022 commented on Feb. 19, 2025, 1:46 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

3

HeroMinhSteve commented on Jan. 27, 2025, 3:28 p.m.

Gợi ý

Cài MANACHER là ra

-7
phanthien10r commented on Sept. 3, 2024, 5:27 p.m.
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
This comment is hidden due to too much negative feedback. Show it anyway.

-1

winky commented on Sept. 2, 2024, 8:11 a.m.

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

5

dienthan901 commented on Feb. 17, 2025, 2:52 p.m.

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

-1

dienthan901 commented on Feb. 17, 2025, 2:52 p.m.

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

-13
DongDuc08 commented on Aug. 20, 2024, 8:53 a.m.
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(); }
This comment is hidden due to too much negative feedback. Show it anyway.

-10
Huy_inIT commented on July 24, 2024, 3:07 a.m.
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;

}
This comment is hidden due to too much negative feedback. Show it anyway.

-3

pndhpndh commented on June 16, 2024, 3:43 a.m.

hihi

-7

chunguyen2k8 commented on May 14, 2024, 12:18 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-5

giga_hedgehog commented on May 15, 2024, 12:49 a.m.

ac

This comment is hidden due to too much negative feedback. Show it anyway.

-5

vantien1526 commented on Aug. 31, 2023, 3:25 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

1

normankr07 commented on Sept. 3, 2023, 4:23 a.m.

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 commented on May 15, 2023, 11:01 a.m.

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

-8

quocdev2009 commented on May 14, 2024, 7:29 a.m.

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é :>>>

This comment is hidden due to too much negative feedback. Show it anyway.

-5

Vinhzn08 commented on July 5, 2024, 5:10 p.m.

orz

This comment is hidden due to too much negative feedback. Show it anyway.

-6

y commented on May 15, 2023, 11:45 a.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-3

YOASOBI commented on Feb. 3, 2023, 1:37 a.m.

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

-4

mt1234 commented on May 18, 2023, 5:50 a.m.

Code kiểu j v :>>

-7

dasher commented on Jan. 27, 2023, 4:53 p.m.

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

This comment is hidden due to too much negative feedback. Show it anyway.

-10

tboros2 commented on Dec. 31, 2022, 12:26 p.m.

Bai nay hash ko on lam ;-;

This comment is hidden due to too much negative feedback. Show it anyway.

-2

OrzSeaPosjtive commented on Dec. 31, 2022, 12:43 p.m.

Tại sao lại k nhỉ

-11

nguyenhainam1012cg commented on March 18, 2023, 3:42 p.m.

tại nó sai =))))

This comment is hidden due to too much negative feedback. Show it anyway.

-28

kh0i commented on June 20, 2022, 6:19 a.m. ← edited →

[deleted]

This comment is hidden due to too much negative feedback. Show it anyway.

61

darkkcyan commented on Nov. 3, 2021, 9:31 p.m.

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 :(.