Every place a pattern appears
For each test you are given a text and a pattern, both lowercase letters. Count the positions in the text where the pattern starts, letter for letter. Appearances may overlap: in aaaa the pattern aa appears 3 times.
Comparing the pattern at every position costs O(n m), too slow when both are long. Aim for O(n + m).
Input
The first line holds T, the number of tests. Each test is two lines: the text, then the pattern.
Output
For each test, one line: how many times its pattern appears in its text.
- Input
3
aaaa
aa
banana
ana
abc
abcd- Output
3
2
0
- aa starts at the first, second and third letter.
- The two appearances share the middle a.
- A pattern longer than the text cannot appear in it.
Limits
1 <= T <= 100the text and the pattern each hold 1 to 100000 lettersall the texts and patterns together hold at most 400000 letters
Hints
Hint 1
When a comparison fails part way, the letters you already matched tell you where the next possible match can start: you never need to look at a text letter twice.
Hint 2
Precompute, for each prefix of the pattern, its longest proper prefix that is also its suffix (the KMP failure function), or run the Z-algorithm on pattern + separator + text.
Where this was reported
- Verizon, On-campus interview, 2021 (GeeksforGeeks)
- Barclays, Summer internship on-campus test, 2020 (GeeksforGeeks)
Our own problem on the task these candidates describe; the wording, examples and tests are InternDoor’s.
Run your code to check it on the examples. Submit runs every hidden test.

