Submission #102232

#	Time	Username	Problem	Language	Result	Execution time	Memory
102232		Kastanda	Palindromes (APIO14_palindrome)	C++11	100 / 100	56 ms	34976 KiB

palindrome

#include<bits/stdc++.h>
using namespace std;
const int MXN = 300005, SGM = 26;
int n, ts, C[MXN][SGM], len[MXN], link[MXN], cnt[MXN];
char S[MXN];
inline int GetLink(int nw, int i)
{
    while (S[i] != S[i - len[nw] - 1])
        nw = link[nw];
    return (nw);
}
inline int Add(int nw, int i)
{
    int ch = S[i] - 'a';
    nw = GetLink(nw, i);
    if (!C[nw][ch])
    {
        ++ ts;
        len[ts] = len[nw] + 2;
        link[ts] = C[GetLink(link[nw], i)][ch];
        C[nw][ch] = ts;
    }
    return (C[nw][ch]);
}
int main()
{
    scanf("%s", S);
    n = strlen(S);
    len[1] = -1; ts = 1;
    link[0] = link[1] = 1;
    int nw = 1;
    for (int i = 1; i <= n; i++)
        nw = Add(nw, i - 1), cnt[nw] ++;
    long long Mx = 0;
    for (int i = ts; i >= 0; i--)
        cnt[link[i]] += cnt[i], Mx = max(Mx, 1LL * cnt[i] * len[i]);
    return !printf("%lld\n", Mx);
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:27:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", S);
     ~~~~~^~~~~~~~~

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