3473. [POJ 3974]最长回文子串

【题目描述】

一个聪明的计算机科学学生安迪正在上一节算法课，教授问学生一个简单的问题：“你能提出一个有效的算法来找出字符串中最大回文的长度吗？”

如果一个字符串前后读的都是相同的，则称其为回文，例如“madam”是回文，而“wdnmd”不是。

学生们认识到这是一个经典的问题，但是没有比迭代所有子串并检查它们是否回文更好的解决方案，显然这个算法根本没有效率，过了一会儿，安迪举起手说：“好的，“我有一个更好的算法”，在他开始解释他的想法之前，他停了一会儿，然后说：“好吧，我有一个更好的算法！”。

如果你认为你知道安迪的最终解决方案，那就证明它吧！给定一个最多1000000个字符的字符串，查找并打印此字符串中最大回文的长度。

【输入格式】

你的程序将在最多30个测试用例上进行测试，每个测试用例在一行中以最多1000000个小写字符的字符串形式给出。输入由以字符串“END”开头的一行结束（为清楚起见，用引号括起来）。

【输出格式】

对于每个样例输出样例号和最大的回文串

【样例输入】

abcbabcbabcba
abacacbaaaab
END

【样例输出】

Case 1: 13
Case 2: 6

【来源】

《算法竞赛进阶指南》

Seventh ACM Egyptian National Programming Contest