#x1070. CF1202E You Are Given Some Strings...

    ID: 6037 远端评测题 3000ms 256MiB 尝试: 5 已通过: 4 难度: 6 上传者: 标签>CF2000提高AC 自动机失败链接贡献汇总前后缀分解贡献法乘法原理2400

CF1202E You Are Given Some Strings...

You Are Given Some Strings...

题面翻译

你有一个字符串 tt 和 nn 个字符串 s1,s2,...,sns_1,s_2,...,s_n,所有字符串都只含有小写英文字母。

令 f(t,s)f(t,s) 为 ss 在 tt 中的出现次数,如 f(′aaabacaa′,′aa′)=3f('aaabacaa','aa')=3,f(′ababa′,′aba′)=2f('ababa','aba')=2.

请计算 ∑i=1n∑j=1nf(t,si+sj)\sum_{i=1}^n\sum_{j=1}^nf(t,s_i+s_j),其中 s+ts+t 代表 ss 和 tt 连接起来。

注意如果存在两对整数 i1,j1,i2,j2i_1,j_1,i_2,j_2,使 si1+sj1=si2+sj2s_{i_1}+s_{j_1}=s_{i_2}+s_{j_2},你需要把 f(t,si1+sj1)f(t,s_{i_1}+s_{j_1}) 和 f(t,si2+sj2)f(t,s_{i_2}+s_{j_2}) 加在答案里。

题目描述

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

Let f(t,s) f(t, s) be the number of occurences of string s s in string t t . For example, f(′aaabacaa′,′aa′)=3 f('\text{aaabacaa}', '\text{aa}') = 3 , and f(′ababa′,′aba′)=2 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 s + t is the concatenation of strings s s and t t . Note that if there are two pairs i1 i_1 , j1 j_1 and i2 i_2 , j2 j_2 such that si1+sj1=si2+sj2 s_{i_1} + s_{j_1} = s_{i_2} + s_{j_2} , you should include both f(t,si1+sj1) f(t, s_{i_1} + s_{j_1}) and f(t,si2+sj2) f(t, s_{i_2} + s_{j_2}) in answer.

输入格式

The first line contains string t t ( 1≤∣t∣≤2⋅105 1 \le |t| \le 2 \cdot 10^5 ).

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

Each of next n n lines contains string si s_i ( 1≤∣si∣≤2⋅105 1 \le |s_i| \le 2 \cdot 10^5 ).

It is guaranteed that ∑i=1n∣si∣≤2⋅105 \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

样例输入 #1

aaabacaa
2
a
aa

样例输出 #1

5

样例 #2

样例输入 #2

aaabacaa
4
a
a
a
b

样例输出 #2

33