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

Please read the guidelines before commenting.

-6
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 ;-;

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

-4

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&lt;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&lt;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;

}

-1

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

hihi

-4

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

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

-2

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

ac

-1

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

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

0

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

0

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ế ạ

-4

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

-1

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

orz

-2

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

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

-1

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

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

-2

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

Code kiểu j v :>>

-6

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.

-8

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.

-1

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

Tại sao lại k nhỉ

-8

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.

53

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