Problem M
Miyazaki's Masterpiece
Hayao Miyazaki is putting together another timeless classic, and he has decided to directly incorporate the desires of his fans into his next masterpiece. His movie consists of $N$ scenes where each scene is meant to convey a certain emotion. It is widely known that the capital letters $A - Z$ represent the $26$ possible human emotions (i.e. happiness with $H$ and disgust with $D$). In order to make their opinions heard, $M$ fans have compiled a list of preferences for what they want to see in the movie. Each fan states that they will be happy if they see some sequence of $L$ emotions (represented by a string of capital letters of length $L$) conveyed in a row in the movie.
Since fans are easily pleased, they will also be a happy if a sequence of emotions is close enough to what they wanted. More specifically, if a sequence of emotions matches all but one or all but two emotions in the desired sequence, they will also be happy.
Miyazaki has been experiencing a bit of writer’s block on making his movie, so he decides to rely on the tried and true tested method to overcome any problem: random generation. He generates a sequence of $N$ scenes from a uniform distribution (where each scene has an equal probability of conveying any emotion). He then gives you the sequence of emotions in the movie and asks you to determine how many fans will be happy with this movie.
Input
The first line of input is three space-separated integers $N \: (1 \leq N \leq 20 \, 000)$, $M \: (1 \leq M \leq 100 \, 000)$, and $L \: (1 \leq L \leq \min (100, N)$), which represent the length of the movie, the number of fans, and the length of each fan’s desired sequence of emotions, respectively.
The next line of the input contains the randomly generated string $S$, which represents the sequence of $N$ emotions conveyed by the movie. Each character in $S$ is an uppercase character from $A - Z$. It is guaranteed that this string has been generated by individually selecting each character from a uniform distribution (each character has a $\frac{1}{26}$ chance of being selected for each position in the string).
The next $M$ lines have a string $f_i$ representing a fan’s desired sequence of emotions (not necessarily distinct). Each character in $f_i$ is an uppercase character from $A - Z$. Fan emotions will not be randomly generated from a uniform distribution, unlike $S$. These fan emotions can be any $L$ length string and may not necessarily be generated independently from the emotions found in the movie.
Your submission will be run on exactly $50$ test cases. The sample is for illustration only.
Each of your submissions will be run on a set of new random test cases.
Output
Output one line containing a single integer, representing the number of fans happy with the random movie.
| Read | Sample Interaction 1 | Write |
|---|
5 3 4 ABCDE BCDE BDDC AEEE
2
