Collapsing Strings
Contest: Educational Codeforces Round 159 (Rated for Div. 2)
Difficulty rating: 1900
Tags: data structures, strings, trees

You are given $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$, consisting of lowercase Latin letters. Let $$$|x|$$$ be the length of string $$$x$$$.

Let a collapse $$$C(a, b)$$$ of two strings $$$a$$$ and $$$b$$$ be the following operation:

- if $$$a$$$ is empty, $$$C(a, b) = b$$$;
- if $$$b$$$ is empty, $$$C(a, b) = a$$$;
- if the last letter of $$$a$$$ is equal to the first letter of $$$b$$$, then $$$C(a, b) = C(a_{1,|a|-1}, b_{2,|b|})$$$, where $$$s_{l,r}$$$ is the substring of $$$s$$$ from the $$$l$$$-th letter to the $$$r$$$-th one;
- otherwise, $$$C(a, b) = a + b$$$, i. e. the concatenation of two strings.

Calculate $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$.

Input format:
The first line contains a single integer $$$n$$$ ($$$1 \le n \le 10^6$$$).

Each of the next $$$n$$$ lines contains a string $$$s_i$$$ ($$$1 \le |s_i| \le 10^6$$$), consisting of lowercase Latin letters.

The total length of the strings doesn't exceed $$$10^6$$$.

Output format:
Print a single integer — $$$\sum\limits_{i=1}^n \sum\limits_{j=1}^n |C(s_i, s_j)|$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Example input:
3
aba
ab
ba

Example output:
20

Example input:
5
abab
babx
xab
xba
bab

Example output:
126

Editorial:
Let's suppose that when we calculate the collapse of two strings $$$a$$$ and $$$b$$$, we reverse the string $$$a$$$ first, so that instead of checking and removing the last letters of $$$a$$$, we do this to the first letters of $$$a$$$. Then, $$$|C(a,b)| = |a| + |b| - 2|LCP(a', b)|$$$, where $$$LCP(a', b)$$$ is the longest common prefix of $$$a'$$$ (the reversed version of $$$a$$$) and $$$b$$$.
Then the answer to the problem becomes $$$2n \sum\limits_{i=1}^{n} |s_i| - 2\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n} LCP(s_i', s_j)$$$.
We need some sort of data structure that allows us to store all strings $$$s_i'$$$ and for every string $$$s_j$$$, calculate the total LCP of it with all strings in the structure. There are many ways to implement it (hashing, suffix arrays, etc), but in our opinion, one of the most straightforward is using a trie.
Build a trie on all strings $$$s_i'$$$. Then, for every vertex of the trie, calculate the number of strings $$$s_i'$$$ that end in the subtree of that vertex (you can maintain it while building the trie: when you add a new string into it, increase this value by $$$1$$$ on every vertex you go through).
If you want to find the $$$LCP$$$ of two strings $$$s$$$ and $$$t$$$ using a trie, you can use the fact that it is equal to the number of vertices that are both on the path to $$$s$$$ and on the path to $$$t$$$ at the same time (except for the root vertex). This method can be expanded to querying the sum of $$$LCP$$$ of a given string $$$s$$$ and all strings in the trie as follows: try to find $$$s$$$ in the trie. While searching for it, you will descend in the trie and go through vertices that represent prefixes of $$$s$$$. For every such prefix, you need the number of strings in the trie that have the same prefix — and it is equal to the number of strings ending in the subtree of the corresponding vertex (which we already calculated). Don't forget that you shouldn't consider the root, since the root represents the empty prefix.
This solution works in $$$O(SA)$$$ or $$$O(S \log A)$$$, where $$$S$$$ is the total length of the strings given in the input and $$$A$$$ is the size of the alphabet.