시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 2048 MB14412210391.150%

문제

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.

예제 입력 1

buzz
8
bee buzz bee buzz bee buzz bee buz

예제 출력 1

3

예제 입력 2

aaa
5
aaaaaaaa aa a aaaa aaa

예제 출력 2

9

예제 입력 3

aba
3
aba ababa abba

예제 출력 3

3

출처

University > University of Alberta Programming Contest > UAPC 2025 > Division 2 C번

  • 문제를 만든 사람: Noah Gergel