TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P2844
  • 题目
  • P2844【APIO2014】回文串
    限制 : 时间限制 : 152000 MS   空间限制 : 131072 KB
    问题描述

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

    输入格式

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

    输出格式

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

    样例输入

    样例输入1:
    abacaba

    样例输入2:
    www

    样例输出

    样例输出1:
    7

    样例输出2:
    4

    提示

    样例说明:
    记|s|为字符串s的长度。对字符串s=s1s2...s|s|,他的字串是一个飞空字符串sisi+1sj,满足1<=i<=j<=|s|。注意s本身也是s的子串。
    一个串是回文的,当且仅当它从左到右读和从右到左读完全一样。
    在第一个样例中,回文子串有7个:a,b,c,aba,aca,bacab,abacaba,其中:
    ·a出现了4次,其价值为41=4
    ·b出现了2次,其价值为2
    1=2
    ·c出现了1次,其价值为11=1
    ·aba出现了2次,其价值为2
    3=6
    ·aca出现了1次,其价值为13=3
    ·bacab出现了1次,其价值为1
    5=5
    ·abacaba出现了1次,其价值为1*7=7
    故最大的回文串价值为7

    数据范围:
    (8分)第一类数据1<=|s|<=100
    (15分)第二类数据1<=|s|<=1000
    (24分)第三类数据1<=|s|<=10000
    (26分)第四类数据1<=|s|<=100000
    (27分)第五类数据1<=|s|<=300000
    共76组测试数据


    来源  感谢nodgd放题