COCI '15 Contest 2 #1 Marko

Points: 5

Time limit: 2.0s

Memory limit: 64M

Problem type

Good old Marko came across a new feature on his mobile phone – T9 input! His phone has a keyboard consisting of numbers looking like this:

1	2 abc	3 def
4 ghi	5 jkl	6 mno
7 pqrs	8 tuv	9 wxyz

In order to input a word using this keyboard, one needs to press a key multiple times for the required letter. More specifically, if the required letter is the first letter mapped to the key, one key press is needed, if it's the second, two key presses are needed and so on. For instance, if we want to input the word giht, we will press the following keys: g-4 i-444 h-44 t-8. The new possibility Marko discovered enables you to input text more easily because you don't need several presses per letter anymore, just one. The software will try to figure out what word from the dictionary you are trying to input.

Marko is quite skeptical of new technologies (at least new for him) and he is afraid that errors will be frequent. That is the reason why he decided to test his hypothesis that the errors are frequent. Marko knows by heart the whole dictionary in the mobile phone. The dictionary consists of $N$ ~N~ words consisting of lowercase letters from the English alphabet, the total length of the word not exceeding $1\,000\,000$ ~1\,000\,000~ characters. He will give an array of key presses $S$ ~S~, of total length at most $1\,000$ ~1\,000~, and wants to know how many words from the dictionary can be mapped to the given array of key presses if the T9 input feature is used.

Input Specification

The first line of input contains the integer $N$ ~N~, the number of words in the dictionary. $(1 \le N \le 1\,000)$ ~(1 \le N \le 1\,000)~. Each of the following $N$ ~N~ lines contains a single word. The last line of input contains the string $S$ ~S~ $(1 \le |S| \le 1\,000)$ ~(1 \le |S| \le 1\,000)~ consisting of digits 2-9.

Output Specification

The first and only line of output must contain the number of words from the dictionary possible to construct from the letters on the keys determined by the string $S$ ~S~.

Sample Input 1

3
tomo
mono
dak
6666

Sample Output 1

Explanation for Sample Output 1

mono is the only word that has all the letters located on key 6.

Sample Input 2

2
ja
la
52

Sample Output 2

Explanation for Sample Output 2

The first letter of both words is located on key 5 and the second letter of both words is located on key 2.

Sample Input 3

3
dom
fon
tom
366

Sample Output 3

Comments

1

Lawlessjoe commented on April 12, 2022, 4:28 a.m.

Hello, is anyone able to help me? I'm getting an invalid return (key error) on most cases, and I just don't know why. All seems good on the test cases. Any help would be much appreciated. Thanks!

2

jebouin commented on May 21, 2022, 7:34 a.m.

Make sure to check your solution for typos :)