ACM ICPC Asia Manila 2009: Problem J

.
Link to blog post: http://raffysaldana.blogspot.com/2009/10/acm-icpc-asia-manila-2009-problem-j.html

2009 ACM ICPC Asia Manila
October 22 – 23, 2009

Problem J: ‘So Long Pal’
Input file: j.in
Output file: stdout
Execution time limit: 120 seconds


A string is a palindrome if it reads the same whether read forward or backward. For example, “MaDaM” and “1234554321” are palindromes, while “APPLE”, “00110”, and “mADam” are not palindromes.

Non-palindromes, however, may also contain palindromes. For example, the longest palindrome in “APPLE” is “PP”, the longest palindrome in “00110” is “0110”, and the longest palindrome in “Philippines” is “ippi”.

Input

The file consists of several test cases, each with a case number and the test case. A test case specifies a string with length 2 up to 100.

Output

For each test case, output the length of the longest palindrome in the string. Note that non-letters and non-digits are considered in searching for palindromes in the string, but are eventually not counted in the length of the longest palindrome.

Sample Input

Case 1: 1234554321
Case 2: Yes
Case 3: M*aD*aM
Case 4: M*aDa*M
Case 5: M*aDa*m
Case 6: 22r1*+00+*1r?
Case 7: ?0&910$$0190+
Case 8: 0&910$0$0+
Case 9: 0&910$+
Case 10: $+*+$

Output for the Sample Input

Case 1: 10
Case 2: 1
Case 3: 1
Case 4: 5
Case 5: 3
Case 6: 6
Case 7: 6
Case 8: 3
Case 9: 1
Case 10: 0


(Acknowledgment: This problem was contributed by Dr. Nelson Marcos, De La Salle University - Manila)

.