1670B.md (3207B)
1 Source: https://codeforces.com/problemset/problem/1670/B 2 3 B. Dorms War 4 5 time limit per test 6 7 1 second 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 Hosssam decided to sneak into Hemose's room while he is sleeping and change his laptop's password. He already knows the password, which is a string $s$ of length $n$. He also knows that there are $k$ special letters of the alphabet: $c_1,c_2,\ldots, c_k$. 22 23 Hosssam made a program that can do the following. 24 25 1. The program considers the current password $s$ of some length $m$. 26 2. Then it finds all positions $i$ ($1\le i \lt m$) such that $s_{i+1}$ is one of the $k$ special letters. 27 3. Then it deletes all of those positions from the password $s$ even if $s_{i}$ is a special character. If there are no positions to delete, then the program displays an error message which has a very loud sound. 28 29 For example, suppose the string $s$ is "abcdef" and the special characters are 'b' and 'd'. If he runs the program once, the positions $1$ and $3$ will be deleted as they come before special characters, so the password becomes "bdef". If he runs the program again, it deletes position $1$, and the password becomes "def". If he is wise, he won't run it a third time. 30 31 Hosssam wants to know how many times he can run the program on Hemose's laptop without waking him up from the sound of the error message. Can you help him? 32 33 Input 34 35 The first line contains a single integer $t$ ($1 \le t \le 10^5$) — the number of test cases. Then $t$ test cases follow. 36 37 The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$) — the initial length of the password. 38 39 The next line contains a string $s$ consisting of $n$ lowercase English letters — the initial password. 40 41 The next line contains an integer $k$ ($1 \le k \le 26$), followed by $k$ distinct lowercase letters $c_1,c_2,\ldots,c_k$ — the special letters. 42 43 It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$. 44 45 Output 46 47 For each test case, print the maximum number of times Hosssam can run the program without displaying the error message, on a new line. 48 49 Example 50 51 Input 52 53 ``` 54 10 55 56 9 57 58 iloveslim 59 60 1 s 61 62 7 63 64 joobeel 65 66 2 o e 67 68 7 69 70 basiozi 71 72 2 s i 73 74 6 75 76 khater 77 78 1 r 79 80 7 81 82 abobeih 83 84 6 a b e h i o 85 86 5 87 88 zondl 89 90 5 a b c e f 91 92 6 93 94 shoman 95 96 2 a h 97 98 7 99 100 shetwey 101 102 2 h y 103 104 5 105 106 samez 107 108 1 m 109 110 6 111 112 mouraz 113 114 1 m 115 ``` 116 117 Output 118 119 ``` 120 5 121 2 122 3 123 5 124 1 125 0 126 3 127 5 128 2 129 0 130 ``` 131 132 Note 133 134 In the first test case, the program can run $5$ times as follows: $\text{iloveslim} \to \text{ilovslim} \to \text{iloslim} \to \text{ilslim} \to \text{islim} \to \text{slim}$ 135 136 In the second test case, the program can run $2$ times as follows: $\text{joobeel} \to \text{oel} \to \text{el}$ 137 138 In the third test case, the program can run $3$ times as follows: $\text{basiozi} \to \text{bioi} \to \text{ii} \to \text{i}$. 139 140 In the fourth test case, the program can run $5$ times as follows: $\text{khater} \to \text{khatr} \to \text{khar} \to \text{khr} \to \text{kr} \to \text{r}$ 141 142 In the fifth test case, the program can run only once as follows: $\text{abobeih} \to \text{h}$ 143 144 In the sixth test case, the program cannot run as none of the characters in the password is a special character.