#2005. [APIO2014] 回文串

    ID: 2005 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>字符串概率论2014APIO后缀自动机SAM统计后缀数组SA回文自动机 PAM

[APIO2014] 回文串

题目描述

给你一个由小写拉丁字母组成的字符串 ss。我们定义 ss 的一个子串的存在值为这个子串在 ss 中出现的次数乘以这个子串的长度。

对于给你的这个字符串 ss,求所有回文子串中的最大存在值。

输入格式

一行,一个由小写拉丁字母(a~z)组成的非空字符串 ss

输出格式

输出一个整数,表示所有回文子串中的最大存在值。

abacaba
7
www
4

提示

【样例解释1】

s\lvert s \rvert 表示字符串 ss 的长度。

一个字符串 s1s2sss_1 s_2 \dots s_{\lvert s \rvert} 的子串是一个非空字符串 sisi+1sjs_i s_{i+1} \dots s_j,其中 1ijs1 \leq i \leq j \leq \lvert s \rvert。每个字符串都是自己的子串。

一个字符串被称作回文串当且仅当这个字符串从左往右读和从右往左读都是相同的。

这个样例中,有 77 个回文子串 a,b,c,aba,aca,bacab,abacaba。他们的存在值分别为 4,2,1,6,3,5,74, 2, 1, 6, 3, 5, 7

所以回文子串中最大的存在值为 77

第一个子任务共 8 分,满足 1s1001 \leq \lvert s \rvert \leq 100

第二个子任务共 15 分,满足 1s10001 \leq \lvert s \rvert \leq 1000

第三个子任务共 24 分,满足 1s100001 \leq \lvert s \rvert \leq 10000

第四个子任务共 26 分,满足 1s1000001 \leq \lvert s \rvert \leq 100000

第五个子任务共 27 分,满足 1s3000001 \leq \lvert s \rvert \leq 300000