33653번 - 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$.

입력

The first line consists of a string $W$ (1ドル≤|W|≤10$). The second line contains a single integer $M$ (1ドル≤M≤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.

출력

Return an integer of the number of times $W$ occurs in $S,ドル allowing for overlap.

제한

힌트