LCC/Moose '19 Contest 5 J5 - 4D Strings

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 10.0s
Memory limit: 512M

Problem types

A string is considered a palindrome if it is the same forwards as it is backwards. For example, aa and racecar are palindromes, while abaa and hello are not.

A string s considers a string t a friend if the concatenation of s and t (s + t) in that order results in a palindrome.

In addition, two strings s and t are close iff both of the following conditions are satisfied:

  1. s considers t a friend or one the strings s considers a friend is close with t.
  2. t considers s a friend or one the strings t considers a friend is close with s.

Given N strings labelled a_1, a_2, \ldots, a_N, can you determine how many pairs of strings are close?

Input Specification

The first line will contain the integer N (1 \le N \le 10^5).

The next line will contain N space-separated strings a_i. a_i will only contain lowercase latin characters and will contain at least one character.

We guarantee that the sum of the string lengths do not exceed 10^6. In other words, \sum_{i=1}^N |a_i| \le 10^6.

Output Specification

Output one integer: the number of pairs of strings that are close. Note that this number may not fit in a 32-bit integer.


Subtask 1 [10%]

N \le 4

Subtask 2 [40%]

N \le 5000

Subtask 3 [50%]

No further constraints.

Sample Input 1

abb a bba bbba

Sample Output 2



There are no comments at the moment.