1084. Z-Box Matches
A print shop checks scanned pages for a recurring watermark. The page is a lowercase string text and the watermark is a lowercase string pattern. A watermark occurrence is a start index i such that the letters text[i], text[i+1], ..., text[i+m-1] are exactly pattern, where m is the length of pattern.
Return how many different start indices i are occurrences. Occurrences may overlap, so inside "zzzz" the pattern "zz" occurs three times. If the pattern is longer than the text, the answer is 0.
A single scan of the text is expected: comparing the pattern against every start position letter by letter is too slow when both strings are long.
Example 1
- Input:
- text = "abababab", pattern = "aba"
- Output:
- 3
- Explanation:
The pattern starts at positions 0, 2 and 4; overlapping occurrences all count.
Example 2
- Input:
- text = "mississippi", pattern = "issi"
- Output:
- 2
- Explanation:
"issi" appears starting at positions 1 and 4, sharing the middle "ssi" letters.
Example 3
- Input:
- text = "hello", pattern = "world"
- Output:
- 0
- Explanation:
The pattern never appears in the text, so the count is 0.
Constraints
1 ≤ text.length, pattern.length ≤ 5 * 105
Both strings consist of lowercase English letters
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n + m)
- Space
- O(n + m)