Submission #307749

#	Time	Username	Problem	Language	Result	Execution time	Memory
307749		richyrich	Palindromes (APIO14_palindrome)	C++17	73 / 100	1089 ms	12444 KiB

palindrome

//#include "shoes.h"
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e5+10;
int tree[N][26], idx, len[N], link[N], t, n, occ[N];
string k;
char s[N];
void init() {
    len[1] = -1, len[2] = 0;
    link[1] = 1, link[2] = 1;
    idx = t = 2;
}
void extend(int p) {
    while(s[p - len[t] - 1] != s[p]) t = link[t];         //WoW
    int x = link[t], c = s[p]-'a';
    if(!tree[t][c])  {
        while(s[p - len[x] - 1] != s[p]) x = link[x];
        tree[t][c] = ++idx;
        len[idx] = len[t] + 2;
        link[idx] = len[idx] == 1 ? 2 : tree[x][c]; 
    }
    t = tree[t][c];
    //printf("%d %d\n", p, t);
    occ[t]++;
}
int main() {
    cin >> k;
    init();
    n = k.size();
    for(int i = 0; i < n; i++) s[i+1] = k[i];
    for(int i = 1; i <= n; i++) extend(i);
    for(int i = idx; i > 2; i--) {
        occ[link[i]] += occ[i];   
    }
    ll ans = 0;
    for(int i = 2; i <= idx; i++) {
        ans = max(ans, (ll)len[i] * occ[i]);
    }
    printf("%lld\n", ans); 
}

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