All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian.
Let us define the palindromeness of a string in the following way:
- If the string is not a palindrome, its' palindromeness is zero.
- The palindromeness of an one-letter string is 1.
- The palindromness of a string S of the length greater than one is 1 + "palindromeness of the string that is formed by the first [|S|/2] symbols of S".
Let us consider some examples for better understanding:
- The palindromeness of the string zxqfd is 0, since the string is not a palindrome.
- The palindromeness of the string a is 1, by definition.
- The palindromeness of the string aa is 2, beucase for "aa" we get 1 + palindromeness of "a", that is one, so we get 2.
- The palindromeness of the string abacaba is 3.
You are given a string S. Find the sum of the palindromenesses of all the non empty substrings of S (i.e. S[i..j], where i <= j). In other words, you have to calculate the sum of palindromenesses of N * (N + 1) / 2 substrings of S, where N is the length of S.
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first and only line of every test case contains a single string S for the corresponding test case.
For each test case, output a single line containing an integer corresponding to the answer to the problem.
- 1 ≤ T ≤ 3
- S consists only of lower-case Latin letters.
Subtask 1 (15 points):
- 1 ≤ |S| ≤ 100
Subtask 2 (23 points):
- 1 ≤ |S| ≤ 1000
Subtask 3 (62 points):
- 1 ≤ |S| ≤ 105
Input: 2 zxqfd aba Output: 5 5
Example case 1: There is no palindrome that occurs as the substring of zxqfd and has the length more than 1. The individual characters are palindromes of the palindromeness of 1.
Example case 2: The palindromeness of aba is 2 and the sum of the palindromenesses of single characters is 3.
|Tags||dfs, ltime23, medium-hard, palindrome, xcwgf666|
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.