拼接两个字符串

题目描述

给定 $N$ 个由小写英文字母组成的字符串 $S_1, S_2, \ldots, S_N$，以及一个由小写英文字母组成的字符串 $T$。

考虑所有 $1$ 到 $N$（含端点）之间的整数对 $(i, j)$，共有 $N^2$ 对。求其中满足以下条件的数对的个数。

按顺序拼接 $S_i$ 和 $S_j$ 得到的字符串包含 $T$ 作为（不要求连续的）子序列。

输入格式

输入按以下格式从标准输入给出：

$N$ $T$
$S_1$
$S_2$
$\vdots$
$S_N$

输出格式

输出答案。

样例

3 bac
abba
bcb
aaca

3

满足题目描述中条件的数对 $(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 作为子序列。

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$。