You Are Given Some Strings...
Contest: Educational Codeforces Round 70 (Rated for Div. 2)
Difficulty rating: 2400
Tags: brute force, string suffix structures, strings

You are given a string $$$t$$$ and $$$n$$$ strings $$$s_1, s_2, \dots, s_n$$$. All strings consist of lowercase Latin letters.

Let $$$f(t, s)$$$ be the number of occurences of string $$$s$$$ in string $$$t$$$. For example, $$$f('\text{aaabacaa}', '\text{aa}') = 3$$$, and $$$f('\text{ababa}', '\text{aba}') = 2$$$.

Calculate the value of $$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$$$, where $$$s + t$$$ is the concatenation of strings $$$s$$$ and $$$t$$$. Note that if there are two pairs $$$i_1$$$, $$$j_1$$$ and $$$i_2$$$, $$$j_2$$$ such that $$$s_{i_1} + s_{j_1} = s_{i_2} + s_{j_2}$$$, you should include both $$$f(t, s_{i_1} + s_{j_1})$$$ and $$$f(t, s_{i_2} + s_{j_2})$$$ in answer.

Input format:
The first line contains string $$$t$$$ ($$$1 \le |t| \le 2 \cdot 10^5$$$).

The second line contains integer $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$).

Each of next $$$n$$$ lines contains string $$$s_i$$$ ($$$1 \le |s_i| \le 2 \cdot 10^5$$$).

It is guaranteed that $$$\sum\limits_{i=1}^{n} |s_i| \le 2 \cdot 10^5$$$. All strings consist of lowercase English letters.

Output format:
Print one integer — the value of $$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j)$$$.

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

Example input:
aaabacaa
2
a
aa

Example output:
5

Example input:
aaabacaa
4
a
a
a
b

Example output:
33

Editorial:
Let's look at any occurrence of arbitrary pair $$$s_i + s_j$$$. There is exactly one special split position, where the $$$s_i$$$ ends and $$$s_j$$$ starts. So, instead of counting occurrences for each pair, we can iterate over the position of split and count the number of pairs. This transformation is convenient, since any $$$s_i$$$, which ends in split position can be paired with any $$$s_j$$$ which starts here.
So, all we need is to calculate for each suffix the number of strings $$$s_i$$$, which starts here, and for each prefix — the number of strings $$$s_i$$$, which ends here. But calculating the prefixes can be transformed to calculating suffixes by reversing both $$$t$$$ and all $$$s_i$$$.
Now we need, for each position $$$pos$$$, calculate the number of strings $$$s_i$$$ which occur from $$$pos$$$. It can be done by Aho-Corasick, Suffix Array, Suffix Automaton, Suffix Tree, but do we really need them since constrains are pretty low? The answer is NO. We can use sqrt-heuristic!
Let's divide all $$$s_i$$$ in two groups: short and long. The $$$s_i$$$ is short if $$$|s_i| \le MAG$$$. There are no more than $$$\frac{\sum{|s_i|}}{MAG}$$$ long strings and, for each such string, we can find all its occurrences with z-function (or prefix-function). It will cost as $$$O(\frac{\sum{|s_i|}}{MAG} \cdot |t| + \sum{|s_i|})$$$.
What to do with short strings? Let's add them to trie! The trie will have $$$O(\sum{|s_i|})$$$ vertices, but only $$$MAG$$$ depth. So we can, for each $$$pos$$$, move down through the trie, while counting the occurrences, using only $$$s[pos..(pos + MAG)]$$$ substring. It will cost us $$$O(|t| \cdot MAG)$$$.
So, if we choose $$$MAG = \sqrt{\sum{|s_i|}}$$$ we can acquire $$$O(\sum{|s_i|} + |t| \sqrt{\sum{|s_i|}})$$$ complexity, using only basic string structures.