Preparando MOJI
Recently, Norge found a string $$$s = s_1 s_2 \ldots s_n$$$ consisting of $$$n$$$ lowercase Latin letters. As an exercise to improve his typing speed, he decided to type all substrings of the string $$$s$$$. Yes, all $$$\frac{n (n + 1)}{2}$$$ of them!
A substring of $$$s$$$ is a non-empty string $$$x = s[a \ldots b] = s_{a} s_{a + 1} \ldots s_{b}$$$ ($$$1 \leq a \leq b \leq n$$$). For example, "auto" and "ton" are substrings of "automaton".
Shortly after the start of the exercise, Norge realized that his keyboard was broken, namely, he could use only $$$k$$$ Latin letters $$$c_1, c_2, \ldots, c_k$$$ out of $$$26$$$.
After that, Norge became interested in how many substrings of the string $$$s$$$ he could still type using his broken keyboard. Help him to find this number.
The first line contains two space-separated integers $$$n$$$ and $$$k$$$ ($$$1 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq 26$$$) — the length of the string $$$s$$$ and the number of Latin letters still available on the keyboard.
The second line contains the string $$$s$$$ consisting of exactly $$$n$$$ lowercase Latin letters.
The third line contains $$$k$$$ space-separated distinct lowercase Latin letters $$$c_1, c_2, \ldots, c_k$$$ — the letters still available on the keyboard.
Print a single number — the number of substrings of $$$s$$$ that can be typed using only available letters $$$c_1, c_2, \ldots, c_k$$$.
7 2 abacaba a b
12
10 3 sadfaasdda f a d
21
7 1 aaaaaaa b
0
In the first example Norge can print substrings $$$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]$$$.
Informação
Provedor Codeforces
Código CF1272C
Tags
Submetido 0
BOUA! 0
Taxa de BOUA's 0%
Datas 09/05/2023 09:57:11
Relacionados