Chef And Palindromes
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef's love for symmetry is well-known. This love is especially expressed for palindromic strings. Today, he has a triplet of strings, <A, B, C>, where each string is consisting of lowercase characters. He is interested in counting the number of ordered triplet of strings <S1, S2, S3> such that S1, S2, and S3 are non-empty substrings of A, B, and C, respectively, and S1 + S2 + S3 is a palindromic string, with '+' denoting the string concatenation operator.
Note that 2 triplets are considered to be different if any substring chosen from a string in 1 triplet is different from the substring chosen from the same string in other triplet. You can check the definition of a substring here.
A string S is palindromic if it reads the same both forward as well as backward. To know more about palindromes, click here.
The first line of input contains a single integer T denoting the number of test cases. First line of each test case contains the string A, second line contains the string B, and the third contains the string C.
For each test case, output the required answer.
- 1 ≤ T ≤ 20
- 1 ≤ |A|, |B|, |C| ≤ 1000
- A, B & C consist of lowercase characters only.
4 a b c ab ba ab ab ab ab aa aa aaOutput
0 6 8 27
- Test 1: No such palindromic string is possible.
- Test 2: "aaa", "bbb", "aba", "bab", "abba", "baab" are all possible palindromic strings.
- Test 3: "aaa", "bbb", "aba", "bab", "abba", "baab", "babab", "ababa" are all possible palindromic strings.
|Tags||cook66, dynamic-programming, ma5termind, medium-hard, palindrome, strings, z-algorithm|
|Time Limit:||5 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.