2016-17 Woburn Challenge Finals Round - Junior Division
Well, this is suspicious… after a year of living in begrudging peace after having been evicted from their homeland of Scarberia, the monkeys have just intercepted a secret message from the cows. The Head Monkey is no fool – this can only mean that her long-time nemesis, Bo Vine, is looking for trouble once again!
The message is a single word, a string consisting of lowercase letters. Knowledge of this word may give the monkeys valuable insight into the cows' military plans, but there are two problems.
The first problem is that the string has been encrypted! Fortunately,
the Head Monkey is well aware of the naive Enigmoo encryption algorithm
which Bo Vine likes to use when transmitting information. Bo Vine has
surely chosen some integral shift value , and then
cyclically shifted each letter in the string forward in the alphabet by
spots. For example, if , then the original message hey
would get encrypted into the string jga
. Note that even Bo Vine
wouldn't have been stupid enough to choose , as that would have
resulted in the encrypted string being equal to the original one.
The second problem is that the message may have been damaged, rendering
some of its letters unreadable. If the monkeys can't identify the -th
letter in the encrypted string, then ?
. It's possible that
all of the letters are still readable, or none of them, or anything in
between.
The Head Monkey has dug out her comprehensive dictionary of cow words, which contains distinct words of length . The -th of these words is , and consists of lowercase letters. Given that the cows may have chosen any possible shift value, and that each unreadable letter in might actually be equal to any lowercase letter, can you help the monkeys narrow their search by counting the number of different words in the dictionary which, when encrypted, might correspond to ? It's possible that the original message is actually some gibberish which doesn't match anything in the dictionary.
In test cases worth of the points, none of the characters in
are equal to ?
.
In test cases worth another of the points, exactly one of the
characters in is equal to ?
.
Input Specification
The first line of input consists of two space-separated integers and
.
The second line of input consists of the string .
lines follow, the -th of which consists of the string
(for ).
Output Specification
Output one line consisting of a single integer – the number of different words in the dictionary which the encrypted string might match.
Sample Input
6 7
??zz?k
attack
cattle
treats
farmer
missed
battle
sleepy
Sample Output
3
Sample Explanation
The original message might have been cattle
– if the cows had chosen
, then the encrypted string would've become igzzrk
, which is
consistent with the message found by the monkeys.
However, the original message might've also been battle
also with
or missed
with .
Comments