记录编号	337617	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	[APIO 2014] Palindromes	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	1.765 s
提交时间	2016-11-04 18:11:28	内存使用	33.32 MiB

//APIO 2014
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <list>
#include <vector>
#include <string>
using namespace std;
char str[300033];
int len[300033];
int cnt[300033];
int fail[300033];
int next[300033][26];
int tot, sum, last, slen;
long long ans;
int read_string()
{
    int len = 2;
    char c;
    while(!isalpha(c = getchar()));
    str[1] = c-'a';
    while(isalpha(c = getchar()))
        str[len++] = c-'a';
    str[len] = 0;
    return len-1;
}
int find(int x)
{
    while(tot-len[x] == 1 || str[tot-len[x]-1] != str[tot])
        x = fail[x];
    return x;
}
int main()
{
    freopen("apio2014_palindrome.in", "r", stdin);
    freopen("apio2014_palindrome.out", "w", stdout);
    slen = read_string();
    sum = 1;
    len[0] = 0;
    len[1] = -1;
    fail[0] = 1;
    last = 1;
    for(int i = 1; i <= slen; i++)
    {
        tot = i;
        int c = find(last);
        if(!next[c][str[i]])
        {
            sum++;
            len[sum] = len[c]+2;
            fail[sum] = next[find(fail[c])][str[i]];
            next[c][str[i]] = sum;
        }
        last = next[c][str[i]];
        cnt[last]++;
    }
    ans = 0;
    for(int i = sum; i >= 2; i--)
    {
        cnt[fail[i]] += cnt[i];
        ans = max(ans, (long long)cnt[i]*len[i]);
    }
    printf("%lld\n", ans);
    return 0;
}