Submission #1319969

#TimeUsernameProblemLanguageResultExecution timeMemory
1319969fatelessPalindromes (APIO14_palindrome)C++20
47 / 100
1096 ms3948 KiB
// #pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;

#define now chrono::steady_clock::now().time_since_epoch().count()
#define speedup cin.tie(0)->sync_with_stdio(0)
#define bitcount(x) __builtin_popcountll(x)
#define lla(x) x.rbegin(), x.rend()
#define all(x) x.begin(), x.end()
#define Tp template <class T>
#define int long long
#define pb push_back
#define vc vector
#define arr array

const int inf = 1e18;
struct HSH {
    int b, mod;
    vc<int> p, pf, sf;
    HSH (string &s, int n, int _b = 39, int _mod = 1e9 + 7) : b(_b), mod(_mod) {
        pf.assign(n + 2, 0); 
        sf.assign(n + 2, 0);
        p.assign(n + 2, 1);
        s = ' ' + s;
        for (int i = 1; i <= n; i++) {
            p[i] = (p[i - 1] * b) % mod;
            pf[i] = (pf[i - 1] * b + (s[i] - 'a' + 1)) % mod;
        } for (int i = n; i >= 1; i--) sf[i] = (sf[i + 1] * b + (s[i] - 'a' + 1)) % mod;
    };

    int getp (int l, int r) {
        return (pf[r] - (pf[l - 1] * p[r - l + 1] % mod) + mod) % mod;
    }

    int gets (int l, int r) {
        return (sf[l] - (sf[r + 1] * p[r - l + 1] % mod) + mod) % mod;
    }
};
inline void solve () {
    int n; string s;
    cin >> s; n = s.size();
    HSH h (s, n, 39, 1e9 + 7);
    auto bs = [&] (int &m1, int &m2) -> void {
        int l = 0, r = n - m2 + 1;
        while (r - l > 1) {
            int mid = (l + r) >> 1;
            if (m1 - mid < 1 || h.getp(m2, m2 + mid) != h.gets(m1 - mid, m1)) r = mid;
            else l = mid; 
        }
        m2 += l;
        m1 -= l;
    };

    int ans = 0;
    unordered_map<int, int> dp;
    for (int i = 2; i < n; i++) {
        int l = i - 1, r = i + 1;
        if (s[l] == s[r] ) {
            bs(l, r);
            while (l < r) {
                int hash = h.getp(l, r);
                // cout << l << ' ' << r << ' ' << hash << '\n';
                dp[hash] += (r - l + 1);
                l++; r--;
            }
        }
    } for (int i = 1; i < n; i++) {
        int l = i, r = i + 1;
        if (s[l] == s[r]) {
            bs(l, r);
            while (l < r) {
                int hash = h.getp(l, r);

                // cout << l << ' ' << r << ' ' << hash << '\n';
                dp[hash] += (r - l + 1);
                l++; r--;
            }
        }
    }
    for (int i = 1; i <= n; i++) dp[h.getp(i, i)]++;
    for (const auto &[x, val] : dp) ans = max(ans, val);

    cout << ans << '\n';
}

signed main() {
    speedup;
    solve();

    return 0;   
}
// aa
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...