← 返回题目列表

AtCoder · abc324_e

H. 连接两根弦

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

分数: 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),串联 abbabcb of S_1 和 S_2 此订单包含 bac 作为子序列。
  • 对于 (i, j) = (1, 3),串联 abbaaaca of S_1 和 S_3 此订单包含 bac 作为子序列。
  • 对于 (i, j) = (2, 3),串联 bcbaaca of 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