分数: 500 点
问题陈述
你被给予 N 字符串 S_1, S_2, \ldots, S_N 由小写英文字母和字符串组成 T 由小写英文字母组成。
有 N^2 对 (i, j) 之间的整数 1 和 N,包括在内。打印其中满足以下条件的对的数量。
- 的串联 S_i 和 S_j 此订单包含 T 作为(不一定是连续的)子序列。
约束
- N 是一个整数。
- 1 \leq N \leq 5 \times 10^5
- S_i 和 T 是长度的字符串 1 to 5 \times 10^5,包含在内,由小写英文字母组成。
- 总长度 S_1, S_2, \ldots, S_N 最多是 5 \times 10^5.
输入
输入由标准输入按以下格式给出:
N T S_1 S_2 \vdots S_N
输出
打印答案。
示例输入 1
3 bac abba bcb aaca
示例输出 1
3
对 (i, j) 满足问题陈述中的条件的是 (1, 2), (1, 3), (2, 3),如下所示。
- 对于 (i, j) = (1, 2),串联
abbabcbof S_1 和 S_2 此订单包含bac作为子序列。 - 对于 (i, j) = (1, 3),串联
abbaaacaof S_1 和 S_3 此订单包含bac作为子序列。 - 对于 (i, j) = (2, 3),串联
bcbaacaof S_2 和 S_3 此订单包含bac作为子序列。
示例输入 2
5 xx x x x x x
示例输出 2
25
示例输入 3
1 y x
示例输出 3
0
示例输入 4
10 ms mkgn m hlms vmsle mxsm nnzdhi umsavxlb ffnsybomr yvmm naouel
示例输出 4
68