AT_abc324_e [ABC324E] Joint Two Strings

题目描述

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

共有 $N^2$ 个由 $1$ 到 $N$ 之间的两个整数组成的有序对 $(i,\ j)$，请输出其中满足以下条件的有序对的个数：

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

输入格式

输入以如下格式从标准输入读入。

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

输出格式

请输出答案。

输入输出样例 #1

输入 #1

3 bac
abba
bcb
aaca

输出 #1

3

输入输出样例 #2

输入 #2

5 xx
x
x
x
x
x

输出 #2

25

输入输出样例 #3

输入 #3

1 y
x

输出 #3

0

输入输出样例 #4

输入 #4

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

输出 #4

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

样例解释 1

满足题目条件的有序对 $(i,\ j)$ 有以下 $3$ 个：$(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 作为子序列。

由 ChatGPT 4.1 翻译