Description:


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

Input:


输入只有一行,为一个只包含小写字母(a -z)的非空字符串s。

Output:


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

Sample Input:


Sample Output:


HINT:


数据满足1≤字符串长度≤300000。

题解:


这个题据称是回文自动机的模板题,然而我蒟蒻我并不会。
参考了某学长的捉法,发现SAM+Manacher比较好实现。
构造后缀自动机,预处理每一个点的出现次数以及在fail树上倍增求祖先。
然后对原串Manacher,如果两个回文串本质不同,后一个必定会更新maxright。
然后对于本质不同的回文串查询一下。

2017.6.10 update


学了一下回文自动机。

又好写又快内存又小呗~