codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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]$.