Submission #209783

#	Time	Username	Problem	Language	Result	Execution time	Memory
209783		jhnah917	Palindromes (APIO14_palindrome)	C++14	0 / 100	694 ms	42080 KiB

palindrome

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

typedef long long ll;
const ll p1 = 179, mod1 = 1e9-63; //2^{64}+1 / 274177

int n;
char s[606060];
int dp[606060];
ll ha[606060], pw[606060];

int pv = 0;
map<ll, int> mp;
int cnt[303030];
int len[303030];
vector<int> g[303030];

void manacher(){
    for(int i=n-1; i>=0; i--){
        s[i << 1 | 1] = s[i];
        s[i << 1] = '#';
    }
    n <<= 1; s[n++] = '#';
    int r = -1, p = -1;
    for(int i=0; i<n; i++){
        dp[i] = (i <= r ? min(dp[p*2-i], r-i) : 0);
        while(i-dp[i]-1 >= 0 && i+dp[i]+1 < n && s[i-dp[i]-1] == s[i+dp[i]+1]) dp[i]++;
        if(i+dp[i] > r) r = i+dp[i], p = i;
    }
}
ll substr(int l, int r){
    __int128_t ret = ha[l] - (__int128_t)ha[r+1] * pw[r-l+1];
    ret %= mod1; ret += mod1; ret %= mod1;
    return ret;
}

void go(int s, int e, ll now){
    if(e-s+1 <= 2) return;
    ll par = substr(s+1, e-1);
    int v = mp[now], u;
    if(!mp.count(par)){
        u = mp[par] = ++pv; len[u] = e-s-1;
    }else return;
    g[u].push_back(v);
    //cout << "add edge : (" << s << ", " << e << ") <- (" << s+1 << ", " << e-1 << ")\n";
    go(s+1, e-1, par);
}

int sz[303030];
void dfs(int v){
    sz[v] = cnt[v];
    for(auto i : g[v]){
        dfs(i); sz[v] += sz[i];
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> s; n = strlen(s);
    pw[0] = 1, pw[1] = p1;
    for(int i=n-1; i>=0; i--) ha[i] = (ha[i+1] * p1 + s[i]) % mod1;
    for(int i=2; i<=n; i++) pw[i] = pw[i-1] * p1 % mod1;
    manacher();

    for(int i=0; i<n; i++){
        if(!dp[i]) continue;
        int s, e;
        if(i & 1) s = i/2-dp[i]/2, e = i/2+dp[i]/2;
        else s = i-dp[i]/2, e = i+dp[i]/2;
        ll now = substr(s, e);
        if(!mp.count(now)){
            mp[now] = ++pv; len[mp[now]] = e-s+1;
        }
        cnt[mp[now]]++;
        go(s, e, now);
    }

    ll ans = 0;
    for(int i=1; i<=pv; i++) if(!sz[i]) dfs(i);
    for(int i=1; i<=pv; i++){
        ans = max(ans, (ll)len[i] * sz[i]);
    }
    cout << ans;
};

// banana

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