Submission #549642

#	Time	Username	Problem	Language	Result	Execution time	Memory
549642		krit3379	Palindromes (APIO14_palindrome)	C++17	100 / 100	38 ms	39124 KiB

palindrome

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

struct node{
    int nxt[26];
    int deg;
    int len;
    int suff;
    long long cnt;
}t[N];

int num,suff;
long long ans;
string s;
queue<int> q;

void add(int pos){
    int cur=suff,idx=s[pos]-'a';
    while(true){
        if(pos-t[cur].len-1>=0&&s[pos-t[cur].len-1]==s[pos])break;
        cur=t[cur].suff;
    }
    if(t[cur].nxt[idx]){
        suff=t[cur].nxt[idx];
        t[suff].cnt++;
        return ;
    }
    t[cur].nxt[idx]=++num;
    t[num].len=t[cur].len+2;
    t[num].cnt++;
    suff=num;
    if(t[num].len==1){
        t[num].suff=2;
        return ;
    }
    while(true){
        cur=t[cur].suff;
        if(pos-t[cur].len-1>=0&&s[pos-t[cur].len-1]==s[pos])break;
    }
    t[num].suff=t[cur].nxt[idx];
    t[t[num].suff].deg++;
}

void init(){
    num=2,suff=2;
    t[1].len=-1,t[1].suff=1;
    t[2].len=0,t[2].suff=1;
}

int main(){
    ios_base::sync_with_stdio(false);cin.tie(nullptr);
    int i,a;
    cin>>s;
    init();
    for(i=0;i<s.length();i++)add(i);
    for(i=3;i<=num;i++)if(!t[i].deg)q.push(i);
    while(!q.empty()){
        a=q.front();
        q.pop();
        if(a<=2)continue;
        t[t[a].suff].cnt+=t[a].cnt;
        if(!--t[t[a].suff].deg)q.push(t[a].suff);
        ans=max(ans,t[a].cnt*t[a].len);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:56:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     for(i=0;i<s.length();i++)add(i);
      |             ~^~~~~~~~~~~

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