F.A.Qs Home Discuss ProblemSet Status Ranklist 1 Contest 入门OJ LoginRegister 捐赠本站
Notice:1:五月份月赛定于5.27日12:30--17:30,鸣谢Claris主持!欢迎大家来玩! 2:关于OJ的注册可看https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671
Problem 3676. -- [Apio2014]回文串

3676: [Apio2014]回文串

Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 3506  Solved: 1629
[Submit][Status][Discuss]

Description

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

Input

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

Output


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

Sample Input

【样例输入l】
abacaba

【样例输入2]
www

Sample Output

【样例输出l】
7

【样例输出2]
4

HINT



一个串是回文的,当且仅当它从左到右读和从右到左读完全一样。

在第一个样例中,回文子串有7个:a,b,c,aba,aca,bacab,abacaba,其中:

● a出现4次,其出现值为4:1:1=4

● b出现2次,其出现值为2:1:1=2

● c出现1次,其出现值为l:1:l=l

● aba出现2次,其出现值为2:1:3=6

● aca出现1次,其出现值为1=1:3=3

●bacab出现1次,其出现值为1:1:5=5

● abacaba出现1次,其出现值为1:1:7=7

故最大回文子串出现值为7。

【数据规模与评分】

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

Source

[Submit][Status][Discuss]

HOME Back