Submission #84071

#	Time	Username	Problem	Language	Result	Execution time	Memory
84071		Bodo171	Palindromes (APIO14_palindrome)	C++14	100 / 100	54 ms	40968 KiB

palindrome

#include <iostream>
#include <fstream>
using namespace std;
const int nmax=300005;
struct fft
{
    int len,link,ap;
    int son[26];
}v[nmax];
string s;
int wh[nmax];
int nodes,p,ch,i;
long long ans;
void primul_chef()
{
    nodes=2;
    v[1].len=-1;
    v[1].link=v[2].link=1;
    wh[0]=2;
}
void ins(int poz)
{
    p=wh[poz-1];ch=s[poz]-'a';
    while(s[poz]!=s[poz-v[p].len-1])
        p=v[p].link;
    if(v[p].son[ch])
    {
        v[v[p].son[ch]].ap++;
        wh[poz]=v[p].son[ch];
        return;
    }
    ++nodes;
    wh[poz]=nodes;
    v[p].son[ch]=nodes;
    v[nodes].len=v[p].len+2;
    v[nodes].ap=1;
    if(v[nodes].len==1)
    {
        v[nodes].link=2;
        return;
    }
    p=v[p].link;
    while(s[poz]!=s[poz-v[p].len-1])
        p=v[p].link;
    v[nodes].link=v[p].son[ch];
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin>>s;s=" "+s;
    primul_chef();
    for(i=1;i<s.size();i++)
        ins(i);
    for(i=nodes;i>=1;i--)
    {
        v[v[i].link].ap+=v[i].ap;
        ans=max(ans,1LL*v[i].len*v[i].ap);
    }
    cout<<ans;
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:52:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(i=1;i<s.size();i++)
             ~^~~~~~~~~

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