Palindrome pairs - MarisaOJ: Marisa Online Judge

Palindrome pairs

Time limit: 1000 ms
Memory limit: 512 MB
Given $n$ string $S_i$. Count the number of pairs $i \neq j$ that $S_iS_j$ is a palindrome. $(i,j)$ is different from $(j,i)$. ### Input - The first line contains an integer $n$. - The next $n$ lines, each line contains a string $S_i$, each string contains only lowercase letters. ### Output - Print the number of pairs. ### Constraints - $1 \le n \le 10^5$. - $1 \le \sum{|S_i|} \le 10^6$ ### Example Input: ``` 3 a b ab ``` Output: ``` 2 ```