All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Given a list of strings S[ 1..N ], you need to count how many ordered pairs of strings are awesome. Given two integers i and j, such that 1 ≤ i, j ≤ n and i ≠ j, an ordered pair ( S[ i ], S[ j ] ) is called awesome if and only if concatenating S[ i ] and S[ j ] gives a palindrome.
The first line contains an integer T denoting the total number of test cases.
In each test case, the first line contains an integer N denoting the total number of strings.
Then, there are N strings, each in a separate line. They only consist of lower case characters.
For each test case, output a single line containing the answer.
- 1 <= T <= 5 In each test case,
- 1 <= N <= 10^6
- Sum of lengths of N strings <= 10^6
Input: 1 3 a ab abb Output: 2
ab|a and abb|a
|Tags||cook63, medium-hard, palindrome, rolling-hash, shangjingbo, strings, trie|
|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.