제출 #486178

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
486178		Turin	회문 (APIO14_palindrome)	C++14	100 / 100	55 ms	112844 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int,int>;

#define ff first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int mod = 1e9 + 7;
const int inf = 1e9 + 9;
const int mx  = 1e6 + 5;

int tree[mx][26], idx;
char s[mx]; int ans[mx];
int len[mx], link[mx], t, occ[mx];

void init(){
    memset(ans, 0, sizeof ans);
    memset(occ, 0, sizeof occ);
    memset(tree, 0, sizeof tree);

    len[1] = -1; link[1] = 1;
    len[2] = 0;  link[2] = 1;
    idx = t = 2;
}

void extend(int p){
    while(s[p-len[t]-1] != s[p]) t=link[t];
    int x = link[t], c = s[p] - 'a';
    while(s[p-len[x]-1] != s[p]) x=link[x];
    if(!tree[t][c]){
        tree[t][c] = ++idx;
        len[idx] = len[t] + 2;
        link[idx] = len[idx] == 1 ? 2 : tree[x][c];
        ans[idx] = 1 + ans[link[idx]];
    }t = tree[t][c]; ++occ[t];
}

ll solve(){
    int n = strlen(s);
    for(int i=0; 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, 1LL*len[i]*occ[i]);
    return ans;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int q = 1; // cin >> q;
    for(int cs=1; cs<=q; ++cs){
        cin >> s; init();
        cout << solve() << "\n";
    }

    return 0;
}

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