Little Petya likes palindromes a lot. Recently he has received a string S, which consists of lowercase letters
of English alphabet and question marks, as a gift from his mother. Each question mark can be replaced with any lowercase English letter with equal probability.
For each position in the string Petya wants to fi nd out an expected value of the length of the longest odd
palindrome centered at that position. A palindrome is considered to be odd if its length is an odd integer.
Output an average value of expected length of the longest odd palindrome for all positions.
There are multiple test cases, terminated by EOF.
Each test case contains a string S (1 <= |S| <= 105). This string can contain only lowercase
letters of English alphabet and question marks.
For each testcase, output should contain one number - the average value of expected length of the longest odd palindrome for all positions. The answer will be considered correct if an absolute or relative error is not greater than 10-6.
ababa ab?bab
2.600000 2.038462
For the rst sample, expected lengths of the longest odd palindromes for each position are: 1, 3, 5, 3, 1.
For the second sample, expected lengths of the longest odd palindromes for each position are: 1, 14/13, 5, 15/13, 3, 1.
Info: 本題輸出為浮點數，絕對或相對誤差 1e-6 以下視為正確
Migrated from old NTUJ.
2011-2012 Petr Summer Camp pE
| No. | Testdata Range | Score |
|---|