Submission #868318

#	Time	Username	Problem	Language	Result	Execution time	Memory
868318		Amdadul	Palindromes (APIO14_palindrome)	C++14	0 / 100	1002 ms	4472 KiB

palindrome

#include<iostream>
#include<string>
#include<vector>
using namespace std;





const int N=2000+5;

int tree[N][26];
int idx,len[N],link[N],cnt[N],t;
string s;
int oc[N];
int ans=0;

void add(int p)
{
    while(s[p-len[t]-1]!=s[p])t=link[t];
    int x=link[t];
    int c=s[p]-'a';

    while(s[p-len[x]-1]!=s[p])x=link[x];

    if(tree[t][c]==0)
    {
        tree[t][c]=++idx;
        len[idx]=len[t]+2;
        link[idx]=len[idx]==1?2:tree[x][c];
        oc[idx]++;
    }
    else oc[tree[t][c]]++;
    t=tree[t][c];


}




int main()
{

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


    cin>>s;
    s='$'+s;
    for(int i=1; i<s.size(); i++)
    {
        add(i);
    }
    long long ans=0;
    vector<int>fre(s.size()+5,0);
    for(int i=s.size()+4; i>=1; i--)
    {
        if(fre[i])continue;

        int x=i;
        long long  tot=0;
        while(x>1)
        {
            tot+=oc[x];
            ans=max(ans,1ll*len[x]*tot);
            fre[x]=1;
            x=link[x];
        }
    }
    cout<< ans <<"\n";

}

Compilation message (stderr)

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

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