You Are Given Some Strings...
题意翻译
你有一个字符串 $t$ 和 $n$ 个字符串 $s_1,s_2,...,s_n$,所有字符串都只含有小写英文字母。
令 $f(t,s)$ 为 $s$ 在 $t$ 中的出现次数,如 $f('aaabacaa','aa')=3$,$f('ababa','aba')=2$.
请计算 $\sum_{i=1}^n\sum_{j=1}^nf(t,s_i+s_j)$,其中 $s+t$ 代表 $s$ 和 $t$ 连接起来。
注意如果存在两对整数 $i_1,j_1,i_2,j_2$,使 $s_{i_1}+s_{j_1}=s_{i_2}+s_{j_2}$,你需要把 $f(t,s_{i_1}+s_{j_1})$ 和 $f(t,s_{i_2}+s_{j_2})$ 加在答案里。
题目描述
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.
输入输出格式
输入格式
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.
输出格式
Print one integer — the value of $ \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(t, s_i + s_j) $ .
输入输出样例
输入样例 #1
aaabacaa
2
a
aa
输出样例 #1
5
输入样例 #2
aaabacaa
4
a
a
a
b
输出样例 #2
33