POJ3974Palindrome
3136+

### Description

Andy the smart computer science student was attending an algorithms class when the professor asked the students a simple question, “Can you propose an efficient algorithm to find the length of the largest palindrome in a string?”

A string is said to be a palindrome if it reads the same both forwards and backwards, for example “madam” is a palindrome while “acm” is not.

The students recognized that this is a classical problem but couldn’t come up with a solution better than iterating over all substrings and checking whether they are palindrome or not, obviously this algorithm is not efficient at all, after a while Andy raised his hand and said “Okay, I’ve a better algorithm” and before he starts to explain his idea he stopped for a moment and then said “Well, I’ve an even better algorithm!”.

If you think you know Andy’s final solution then prove it! Given a string of at most 1000000 characters find and print the length of the largest palindrome inside this string.

### Input

Your program will be tested on at most 30 test cases, each test case is given as a string of at most 1000000 lowercase characters on a line by itself. The input is terminated by a line that starts with the string “END” (quotes for clarity).

### Output

For each test case in the input print the test case number and the length of the largest palindrome.

Sample Input

abcbabcbabcba
abacacbaaaab
END

### Sample Output

Case 1: 13
Case 2: 6

# 解题思路

Manacher算法是这样的，从左到右依次计算以每个字符为对称中心的最长回文长度，如果下一个字符包含在前一个回文串中，那么由对称性可知其在回文区域内的最长回文长度。如对称中心是i，回文向右扩展的长度是c[i]（包括s[i]），如果j在[i, i+c[i])范围内，那么cspan style="color: #ff0000;">j = cstrong>i*2-j或者c[j] = i+c[i] – j，即要么是跟前面一样多，要么是超出回文区域被截取了。当然，这只是至少的情况，后面还需要继续扩展，当s[i+c[i == s[i-c[i时，回文区域就会扩大。由于回文区域右边界最大就扩展到n，区域内的可以根据对称性O(1)求出回文长度，因此整体复杂度是O(n)。