Submission #997459

#	Time	Username	Problem	Language	Result	Execution time	Memory
997459		vjudge1	Palindromes (APIO14_palindrome)	C++17	23 / 100	1088 ms	1000 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

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

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

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

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

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

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

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

    int ans = 0;

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

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

        for (int i = 1; i + len - 1 < n; i ++){
                hsh = (1ll * hsh - 1ll * base_pwr[0][len - 1] * s[i - 1]) % mod[0];
                hsh = (1ll * 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 = (1ll * hsh0 * inv[0]) % mod[0];
                hsh0 = (1ll * hsh0 + 1ll * 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