LCC '22 Contest 5 S1 - Jimmy's Spelling Bee

View as PDF

Submit solution

Points: 5
Time limit: 1.5s
Memory limit: 128M

Author:
Problem type

As should be obvious from his time at Mackenzie, Jimmy is a professional Spelling Bee-er. Of course, after his brief stint as MCPT Competitive Vice President, he forgot much of the convoluted vocabulary he once knew. However, undeterred by such a hindrance in his quest to restore himself to his former glory in the 2023 National Spelling Bee, he has turned to the next best option: cheating.

The day is now here, and Jimmy is standing at the podium, ready to hear the word he must spell. He already compiled a list of N words that are likely to be asked in the spelling bee and entered their spellings into a phone that he most definitely did not sneak into the competition. He is asked to spell a word, and of course he doesn't know the exact spelling, but from his past experience as a professional spelling bee-er, he knows the length of the word and where some of the letters go. Given a list of possible words, can you figure out which words could be the word he heard?

Note: It is recommended for Python users to use Pypy

Constraints

1\le N\le 10^5

The length of each word is at most 100.

Input Specification

The first line contains N, the number of words.

The second line contains S, a string consisting of lowercase latin characters or the character _. A character that is _ means that the letter in that position could be anything, while a lowercase letter means that Jimmy is certain that the letter there is the correct letter.

The next N lines contain a string C_i, a word that could be asked at the spelling bee.

Output Specification

The first line contains K, the number of potential words.

The next K lines each contain a string P_i, a word that is consistent with the information Jimmy deduced. Output the strings in the order of the input (if there are duplicates, do print them multiple times).

Sample Input

5
__pl_
apple
opppl
apples
app
haply

Sample Output

2
apple
haply

Sample Explanation

Firstly, the word must have 5 letters. This eliminates apples and app. Next, the third letter must be p and the fourt l. The only valid answers are thus apple and haply.


Comments

There are no comments at the moment.