← 返回题目列表

Codeforces · 1202/E

E. 给你一些字符串......

中文机器翻译题面 查看原题

给定一个字符串 $$$t$$$ 和 $$$n$$$ 字符串 $$$s_1, s_2, \dots, s_n$$$。所有字符串均由小写拉丁字母组成。

令 $$$f(t, s)$$$ 为字符串 $$$s$$$ 在字符串 $$$t$$$ 中出现的次数。例如,$$$f('\text{aaabacaa}', '\text{aa}') = 3$$$,$$$f('\text{ababa}', '\text{aba}') = 2$$$。

计算 $$$\sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} f(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})$$$ 的答案。

输入

第一行包含字符串 $$$t$$$ ($$$1 \le |t| \le 2 \cdot 10^5$$$)。

第二行包含整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$)。

接下来的 $$$n$$$ 行都包含字符串 $$$s_i$$$ ($$$1 \le |s_i| \le 2 \cdot 10^5$$$)。

保证 $$$\sum\limits_{i=1}^{n} |s_i| \le 2 \cdot 10^5$$$。所有字符串均由小写英文字母组成。

输出

打印一个整数 — $$$\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