제출 #997456

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
997456		vjudge1	회문 (APIO14_palindrome)	C++17	23 / 100	1056 ms	5608 KiB

palindrome

#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 ans = 0;

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

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

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

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

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

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

    cout << ans << endl;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 0 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27