Palindrome dài nhất

View as PDF

Submit solution


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

3

Comments

Please read the guidelines before commenting.



  • 0
    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;
    

    }


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

    hihi


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

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


  • 0
    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


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


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


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

        orz


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

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


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

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


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

      Code kiểu j v :>>


  • -3
    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


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

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


  • -27
    kh0i  commented on June 20, 2022, 6:19 a.m. edited

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


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


    • -12
      tboros2  commented on Dec. 30, 2022, 11:34 a.m.

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


  • 55
    I_love_Hoang_Yen  commented on Aug. 23, 2021, 11:25 a.m.

    Mình vừa thêm 1 test do bạn manhtranVN đóng góp, và có vài submission đã mất AC.