Submission #1186671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1186671		irmuun	회문 (APIO14_palindrome)	C++17	100 / 100	77 ms	103888 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

struct Node{
    ll nxt[26],sufflink;
    ll len,cnt;
    vector<ll>edges;
}tree[300005];

string s;
ll suf,num,ans=0;

void init(){
    num=2,suf=2;
    tree[1].len=-1; tree[1].sufflink=1;
    tree[2].len=0; tree[2].sufflink=1;
    tree[1].edges.pb(2);
}

void add(ll pos){
    ll cur=suf,cur_len=0;
    ll x=s[pos]-'a';
    while(true){
        cur_len=tree[cur].len;
        if(pos-1-cur_len>-1&&s[pos-1-cur_len]==s[pos]) break;
        cur=tree[cur].sufflink;
    }
    if(tree[cur].nxt[x]!=0){
        suf=tree[cur].nxt[x];
        tree[suf].cnt++;
        return;
    }
    suf=++num;
    tree[num].len=tree[cur].len+2;
    tree[num].cnt=1;
    tree[cur].nxt[x]=num;
    if(tree[num].len==1){
        tree[num].sufflink=2;
        tree[2].edges.pb(num);
        return;
    }
    while(true){
        cur=tree[cur].sufflink;
        cur_len=tree[cur].len;
        if(pos-1-cur_len>-1&&s[pos-1-cur_len]==s[pos]){
            tree[num].sufflink=tree[cur].nxt[x];
            tree[tree[cur].nxt[x]].edges.pb(num);
            break;
        }
    }
}
void dfs(ll i){
    for(ll j:tree[i].edges){
        dfs(j);
        tree[i].cnt+=tree[j].cnt;
    }
    ans=max(ans,tree[i].len*tree[i].cnt);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>s;
    init();
    for(ll i=0;i<s.size();i++){
        add(i);
    }
    dfs(1);
    cout<<ans;
}

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