You are given a text and a pattern. Scan the text from left to right and greedily match the pattern: whenever the pattern is found starting at the current position, count it and jump forward past the whole matched block (so matches never overlap); otherwise advance by one position. Print how many non-overlapping matches you collect.
Because the scan is left-to-right and greedy, the count is uniquely determined. For instance, in aaaa the pattern aa matches at positions 0 and 2 for a count of 2 (it does not also count the overlapping match at position 1).
Line 1: the text, a string of lowercase English letters. Line 2: the pattern, a non-empty string of lowercase English letters.
A single integer: the number of non-overlapping, left-to-right greedy matches of the pattern in the text.
a-z.Example 1
Input
ababab ab
Expected
3
Explanation
ab matches at positions 0, 2, and 4 with no overlap, so the count is 3.
Example 2
Input
banana ana
Expected
1
Explanation
The first ana is matched at position 1; the scan then jumps past it, so the overlapping ana at position 3 is not counted. The answer is 1.
Ready to solve this?
Sign in to open the editor, run your code against the sample tests, and submit against the full test suite.
Sign in to solve →