|시간 제한||메모리 제한||제출||정답||맞힌 사람||정답 비율|
|1 초||512 MB||23||6||5||23.810%|
A palindrome is a word that reads the same backwards as forwards. For example, “
abba” and “
anavolimilovana” are palindromes A sample is a string of one or more lower case letters of the English alphabet, and the weight of a sample is the number of its substrings (words) that are palindromes, counting each word occurrence separately.
More precisely, let w be a sample of length n. The word wa,b is obtained by taking all characters from position a to position b in sample w. The weight of sample w is defined as the number of different pairs of integers a, b (1 ≤ a ≤ b ≤ n) such that the word wa,b is a palindrome.
You are given the sample w. It can either be left unchanged, or exactly one position can be chosen and the letter on that position arbitrarily changed. Find the maximal possible sample weight that can be obtained as described above.
The first line of input contains the given sample w – a string of lower case letters of the English alphabet.
You must output the required maximal possible weight.
1 ≤ n ≤ 100
101 ≤ n ≤ 5 000
5001 ≤ n ≤ 100 000
Clarification of the first example: Each substring from the sample already is a palindrome, so it is best left unchanged.
Clarification of the second example: If we change the second letter of the sample to “c”, we will get the sample “bcccb” with a weight of 9.