Submission #557402

#	Time	Username	Problem	Language	Result	Execution time	Memory
557402		stefantaga	Palindromes (APIO14_palindrome)	C++14	0 / 100	1098 ms	36184 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;
string s;
struct PalTree
{
    int urm[27];
    int sufflink;
    int lung;
    int num;
}V[300005];
int suff,num;
void InitPalTree()
{
    num=2;
    suff=2;
    V[1].lung=-1;V[1].sufflink=1;
    V[2].lung=0; V[2].sufflink=1;
}
void adauga(int poz)
{
    int curr = suff;
    int letter = s[poz]-'a';
    while (true)
    {
        int lung = V[curr].lung;
        if (poz-lung-1>=0&&s[poz-lung-1]==s[poz])
        {
            break;
        }
        curr=V[curr].sufflink;
    }
    if (V[curr].urm[letter])
    {
        suff=curr;
        V[suff].num++;
        return;
    }
    num++;
    suff=num;
    V[curr].urm[letter]=num;
    V[num].lung=V[curr].lung+2;
    V[num].num=1;
    if (V[num].lung==1)
    {
        V[num].sufflink=2;
        return;
    }
    while (true)
    {
        curr=V[curr].sufflink;
        int lung = V[curr].lung;
        if (poz-lung-1>=0&&s[poz-lung-1]==s[poz])
        {
            V[num].sufflink=V[curr].urm[letter];
            break;
        }
    }
    return;
}
int i;
long long rasp;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>s;
    InitPalTree();
    for (i=0;i<s.size();i++)
    {
        adauga(i);
    }
    for (i=num;i>=1;i--)
    {
        rasp=max(rasp,1LL*V[i].num*V[i].lung);
        V[V[i].sufflink].num+=V[i].num;
    }
    cout<<rasp;
    return 0;
}

Compilation message (stderr)

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

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