Proper String Problem

A proper prefix of a string s is a prefix of s that is not s itself. A proper suffix of s is defined the same way, using suffixes.

For two strings s and t, let f(s, t) be the length of the longest string that is both a proper suffix of s and a proper prefix of t.

You are given n strings s1, s2, ..., sn, each made only of the characters A, C, G, and T. No string is a substring of another string in the list.

Compute $\sum_{i=1}^{n} \sum_{j=1}^{n} f(s_i, s_j)$.

The first line contains the number of strings n (1 to 100,000).

Each of the next n lines contains one string s1, s2, ..., sn made only of A, C, G, and T. No string is a substring of another string in the list. The total length of all n strings is at most $10^7$.

The empty string can be a proper prefix or a proper suffix.

In the sample input, f(s1, s1) = 4, f(s2, s1) = 6, f(s3, s1) = 6, f(s4, s1) = 3, and f(s4, s2) = 4. The other 11 values are all 0. The answer is 4 + 6 + 6 + 3 + 4 = 23.