1272C.md (1957B)
1 Source: https://codeforces.com/problemset/problem/1272/C 2 3 C. Yet Another Broken Keyboard 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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! 22 23 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". 24 25 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$. 26 27 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. 28 29 Input 30 31 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. 32 33 The second line contains the string $s$ consisting of exactly $n$ lowercase Latin letters. 34 35 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. 36 37 Output 38 39 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$. 40 41 Examples 42 43 Input 44 45 ``` 46 7 2 47 abacaba 48 a b 49 ``` 50 51 Output 52 53 ``` 54 12 55 ``` 56 57 Input 58 59 ``` 60 10 3 61 sadfaasdda 62 f a d 63 ``` 64 65 Output 66 67 ``` 68 21 69 ``` 70 71 Input 72 73 ``` 74 7 1 75 aaaaaaa 76 b 77 ``` 78 79 Output 80 81 ``` 82 0 83 ``` 84 85 Note 86 87 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]$.