Problem C
Search Wizard
You adore word searches, and have been doing them since you were little. You do them so much, you started just picking out words whenever you see a string of text! With a target string $W$ in mind, can you figure out how many times $W$ occurs in the string $S$?
Note that instances of $W$ may overlap partially, but every occurance has a unique starting index in $S$.
Input
The first line consists of a string $W$ ($1 \leq |W| \leq 10$). The second line contains a single integer $M$ ($1 \leq M \leq 10^5$). The third and final line contains the string $S$ consisting of $M$ words. Consecutive words are separated by a single space. The total length of all words in $S$ is at most $10^5$. The only characters that will appear in $W$ and all words in $S$ are lowercase alphabetical characters a - z.
Output
Return an integer of the number of times $W$ occurs in $S$, allowing for overlap.
| Sample Input 1 | Sample Output 1 |
|---|---|
buzz 8 bee buzz bee buzz bee buzz bee buz |
3 |
| Sample Input 2 | Sample Output 2 |
|---|---|
aaa 5 aaaaaaaa aa a aaaa aaa |
9 |
| Sample Input 3 | Sample Output 3 |
|---|---|
aba 3 aba ababa abba |
3 |
