All submissions for this problem are available.
A string is called beautiful if it has the form AArAAr where A is some non-empty string and Ar is the reversed A.
You are given a string S composed only of lowercase letters of the English alphabet. Find the number of its beautiful substrings. Equal substrings in different positions are considered different. For example, the string aaaaa has 2 different substrings because we have beautiful substring aaaa in two different positions.
The first line contains a single integer T <= 10, the number of test cases. T test cases follow. The only line of each test case contains a non-empty string composed only of lowercase letters of the English alphabet. The length of the string is not greater than 100000.
For each test case, output a single line containing the number of beautiful substrings of the corresponding string.
Input: 6 aaaa aaaaa abbaabba abbaabb abaaba xxyyxxxxyyxx Output: 1 2 1 0 0 2
|Tags||anton_lunyov, cook08, medium|
|Time Limit:||0.24 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, 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, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.