Joint Two Strings

题目描述

给你 $N$ 个由小写英文字母组成的字符串 $S_1, S_2, \ldots, S_N$，以及一个由小写英文字母组成的字符串 $T$。 共有 $N^2$ 个整数对 $(i, j)$，其中 $i, j$ 的取值范围都是 $1$ 到 $N$（含）。请输出满足下述条件的整数对的数量。

按此顺序将 $S_i$ 与 $S_j$ 连接起来的字符串包含 $T$ 作为（不必连续的）子序列。

输入格式

输入按下述格式由标准输入提供： $N$ $T$ $S_1$ $S_2$ $\vdots$ $S_N$

输出格式

输出答案。

3 bac
abba
bcb
aaca

3

5 xx
x
x
x
x
x

25

1 y
x

0

10 ms
mkgn
m
hlms
vmsle
mxsm
nnzdhi
umsavxlb
ffnsybomr
yvmm
naouel

68

提示

$N$ 是一个整数。 $1 \leq N \leq 5 \times 10^5$ $S_i$ 和 $T$ 的长度都是 $1$ 到 $5 \times 10^5$ 之间的字符串，且由小写英文字母组成。 $S_1, S_2, \ldots, S_N$ 的总长度至多为 $5 \times 10^5$。满足题目条件的整数对 $(i, j)$ 为 $(1, 2), (1, 3), (2, 3)$，如下所示。

对于 $(i, j) = (1, 2)$，$S_1$ 和 $S_2$ 按此顺序连接得到的字符串 $abbabcb$ 包含 $bac$ 作为子序列。 对于 $(i, j) = (1, 3)$，$S_1$ 和 $S_3$ 按此顺序连接得到的字符串 $abbaaaca$ 包含 $bac$ 作为子序列。 对于 $(i, j) = (2, 3)$，$S_2$ 和 $S_3$ 按此顺序连接得到的字符串 $bcbaaca$ 包含 $bac$ 作为子序列。

标签: AtCoder|abc324E

来源

AtCoder|abc324E