Submission #997341

#TimeUsernameProblemLanguageResultExecution timeMemory
997341vjudge1Palindromes (APIO14_palindrome)C++17
23 / 100
1065 ms5612 KiB
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll mod[2] = {ll(1e9 + 7), ll(1e9 + 9)};
const ll base[2] = {ll(727), ll(1e6 + 1)};
const ll N = 3e5 + 10;

string s;
ll n, base_pwr[2][N], inv[2];

ll pwr(ll a, ll b, ll id){
    if (b < 0) return 0;
    if (b == 0) return 1;

    ll val = pwr(a, b / 2, id);
    val *= val;
    val %= mod[id];

    if (b % 2) val *= a;
    return val % mod[id];
}

int main(){
    for (ll j = 0; j < 2; j ++){
        base_pwr[j][0] = 1;
        inv[j] = pwr(base[j], mod[j] - 2, j);
        for (ll i = 1; i < N; i ++)
            base_pwr[j][i] = base_pwr[j][i - 1] * base[j] % mod[j];
    }

    cin >> s;
    n = s.size();

    ll l = 1;
    ll r = n + 1;

    while (r - l > 1){
        ll len = (l + r) / 2;
        ll hsh0[2] = {0}, hsh[2] = {0};
        map<pair<ll, ll>, ll> cnt;
    
        ll mx_occur = 0;
        for (ll i = 0; i < len; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
            }
        }

        if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
            cnt[{hsh[0], hsh[1]}]++;
            mx_occur = 1;
        }

        for (ll i = 1; i + len - 1 < n; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
                hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
                hsh[j] = (hsh[j] + mod[j]) % mod[j];

                hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
                hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
            }

            if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
                cnt[{hsh[0], hsh[1]}]++;
                mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
            }
        }

        // cout << len << " -- " << mx_occur << endl;

        if (mx_occur >= len)
            l = len;
        else 
            r = len;
    }

    ll ans = 0;
    for (ll len = max(1ll, l - 2); len <= min(l + 2, n); len ++){
        ll hsh0[2] = {0}, hsh[2] = {0};
        map<pair<ll, ll>, ll> cnt;
    
        ll mx_occur = 0;
        for (ll i = 0; i < len; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
            }
        }

        if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
            cnt[{hsh[0], hsh[1]}]++;
            mx_occur = 1;
        }

        for (ll i = 1; i + len - 1 < n; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
                hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
                hsh[j] = (hsh[j] + mod[j]) % mod[j];

                hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
                hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
            }

            if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
                cnt[{hsh[0], hsh[1]}]++;
                mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
            }
        }

        ans = max(ans, len * mx_occur);
    }

    for (ll len = max(1ll, n - 5); len <= n; len ++){
        ll hsh0[2] = {0}, hsh[2] = {0};
        map<pair<ll, ll>, ll> cnt;
    
        ll mx_occur = 0;
        for (ll i = 0; i < len; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
            }
        }

        if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
            cnt[{hsh[0], hsh[1]}]++;
            mx_occur = 1;
        }

        for (ll i = 1; i + len - 1 < n; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
                hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
                hsh[j] = (hsh[j] + mod[j]) % mod[j];

                hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
                hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
            }

            if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
                cnt[{hsh[0], hsh[1]}]++;
                mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
            }
        }

        ans = max(ans, len * mx_occur);
    }

    for (ll len = 1; len <= n; len ++){
        ll hsh0[2] = {0}, hsh[2] = {0};
        map<pair<ll, ll>, ll> cnt;
    
        ll mx_occur = 0;
        for (ll i = 0; i < len; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] * base[j] + s[i]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][i] * s[i]) % mod[j];
            }
        }

        if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
            cnt[{hsh[0], hsh[1]}]++;
            mx_occur = 1;
        }

        for (ll i = 1; i + len - 1 < n; i ++){
            for (ll j = 0; j < 2; j ++){
                hsh[j] = (hsh[j] - base_pwr[j][len - 1] * s[i - 1]) % mod[j];
                hsh[j] = (hsh[j] * base[j] + s[i + len - 1]) % mod[j];
                hsh[j] = (hsh[j] + mod[j]) % mod[j];

                hsh0[j] = (hsh0[j] - s[i - 1] + mod[j]) % mod[j]; 
                hsh0[j] = (hsh0[j] * inv[j]) % mod[j];
                hsh0[j] = (hsh0[j] + base_pwr[j][len - 1] * s[i + len - 1]) % mod[j];
            }

            if (hsh[0] == hsh0[0] and hsh[1] == hsh0[1]){
                cnt[{hsh[0], hsh[1]}]++;
                mx_occur = max(mx_occur, cnt[{hsh[0], hsh[1]}]);
            }
        }

        ans = max(ans, len * mx_occur);
    }

    cout << ans << endl;
}
#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...