Submission #597878

#	Time	Username	Problem	Language	Result	Execution time	Memory
597878		Hanksburger	Palindromes (APIO14_palindrome)	C++17	73 / 100	1082 ms	12380 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
int nxt[100005][26], len[100005], suff[100005], freq[100005], cur=1, cnt=2;
string s;
void add(int x)
{
    while (s[x-len[cur]-1]!=s[x])
        cur=suff[cur];
    int y=s[x]-'a';
    if (nxt[cur][y])
    {
        cur=nxt[cur][y];
        freq[cur]++;
        return;
    }
    nxt[cur][y]=++cnt;
    len[cnt]=len[cur]+2;
    freq[cnt]++;
    if (len[cnt]==1)
    {
        suff[cnt]=2;
        cur=cnt;
        return;
    }
    do cur=suff[cur];
    while (s[x-len[cur]-1]!=s[x]);
    suff[cnt]=nxt[cur][y];
    cur=cnt;
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    len[1]=-1;
    suff[1]=suff[2]=1;
    cin >> s;
    for (int i=0; i<s.length(); i++)
        add(i);
    long long ans=0;
    for (int i=cnt; i>=3; i--)
    {
        ans=max(ans, 1LL*freq[i]*len[i]);
        freq[suff[i]]+=freq[i];
    }
    cout << ans;
    return 0;
}

Compilation message (stderr)

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

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