← 返回题目列表

Codeforces · 1272/C

C. 又一个坏了的键盘

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

最近,Norge 发现了一个由 $$$n$$$ 小写拉丁字母组成的字符串 $$$s = s_1 s_2 \ldots s_n$$$。作为提高打字速度的练习,他决定键入字符串 $$$s$$$ 的所有子字符串。是的,所有 $$$\frac{n (n + 1)}{2}$$$!

$$$s$$$ 的子字符串是非空字符串 $$$x = s[a \ldots b] = s_{a} s_{a + 1} \ldots s_{b}$$$ ($$$1 \leq a \leq b \leq n$$$)。例如,“auto”和“ton”是“automaton”的子字符串。

练习开始后不久,Norge 意识到他的键盘坏了,即他只能使用 $$$26$$$ 中的 $$$k$$$ 拉丁字母 $$$c_1, c_2, \ldots, c_k$$$。

之后,Norge 开始感兴趣的是,他仍然可以使用损坏的键盘输入字符串 $$$s$$$ 的多少个子字符串。帮他找到这个号码。

输入

第一行包含两个空格分隔的整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq 26$$$) — 字符串 $$$s$$$ 的长度以及键盘上仍然可用的拉丁字母的数量。

第二行包含字符串 $$$s$$$,由 $$$n$$$ 小写拉丁字母组成。

第三行包含 $$$k$$$ 以空格分隔的不同小写拉丁字母 $$$c_1, c_2, \ldots, c_k$$$ — 这些字母在键盘上仍然可用。

输出

打印单个数字 — 仅可使用可用字母 $$$c_1、c_2、\ldots、c_k$$$ 键入的 $$$s$$$ 子字符串的数量。

示例

输入 #1

7 2
abacaba
a b

输出 #1

12

输入 #2

10 3
sadfaasdda
f a d

输出 #2

21

输入 #3

7 1
aaaaaaa
b

输出 #3

0

注意

在第一个示例中,Norge 可以打印子字符串 $$$s[1\ldots2]$$$、$$$s[2\ldots3]$$$、$$$s[1\ldots3]$$$、$$$s[1\ldots1]$$$、$$$s[2\ldots2]$$$、 $$$s[3\ldots3]$$$、$$$s[5\ldots6]$$$、$$$s[6\ldots7]$$$、$$$s[5\ldots7]$$$、$$$s[5\ldots5]$$$、$$$s[6\ldots6]$$$、$$$s[7\ldots7]$$$。