Description

考虑一个只包含小写拉丁字母的字符串 \(S\). 我们定义 \(S\) 的一个子串 \(T\) 的 “出现值” 为 \(T\) 在 \(S\) 中的出现次数乘以 \(T\) 的长度. 请你求出 \(S\) 的所有回文子串中的最大出现值.

Input

输入只有一行, 为一个只包含小写字母的非空字符串 \(S\).

Output

输出一个整数, 为所查回文子串的最大出现值.

Sample Input

abacaba

Sample Output

7

Data Range

数据满足:\(1 \leq |S| \leq 300000\).

Explanation

这道题用回文串自动机做比较方便, 但是除了这道题似乎没有别的什么卵用.

当然也可以用 SAM+Manacher......

传送门:http://blog.csdn.net/u013368721/article/details/42100363

听说这个自动机是一个俄国人发明的:http://codeforces.com/blog/entry/13959

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;
typedef long long lli;
const int maxn = 300100;

class PalindromeAutomaton
{
public:
    int n, ncnt, last;
    int ch[maxn][26], par[maxn], len[maxn];
    int size[maxn];
    char* str;
    void init(int n, char str[])
    {
        this->n = n;
        this->str = str;
        ncnt = 1;
        par[0] = par[1] = 1;
        len[1] = -1;
        return ;
    }

    void insert(int c, int l)
    {
        int p = last;
        while (str[l - len[p] - 1] != str[l])
            p = par[p];
        if (!ch[p][c]) {
            int now = ++ncnt,
                q = par[p];
            len[now] = len[p] + 2;
            while (str[l - len[q] - 1] != str[l])
                q = par[q];
            par[now] = ch[q][c];
            ch[p][c] = now;
        }
        last = ch[p][c];
        size[last] += 1;
        return ;
    }
    lli eval(void)
    {
        lli res = 0;
        for (int i = ncnt; i > 0; i--) {
            size[par[i]] += size[i];
            res = max(res, (lli)size[i] * len[i]);
        }
        return res;
    }
} pam;

int n;
char str[maxn];

int main(int argc, char** argv)
{
    scanf("%s", str + 1);
    n = strlen(str + 1);
    pam.init(n, str);
    for (int i = 1; i <= n; i++)
        pam.insert(str[i] - 'a', i);
    lli res = pam.eval();
    printf("%lld\n", res);
    return 0;
}