Write a generator for substring pattern matches
Company: Apple
Role: Machine Learning Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
## Problem
Write a generator that scans a string and emits a value whenever a substring matches a given pattern.
### Input
- A string `s`
- A string `pattern` (non-empty)
### Output
Return a generator/iterator that yields `True` **once for each occurrence** of `pattern` in `s`, scanning from left to right. Matches may overlap.
### Examples
- `s = "aaaa"`, `pattern = "aa"` → yields `True` 3 times (matches at indices 0, 1, 2)
- `s = "abc"`, `pattern = "d"` → yields nothing
### Constraints
- `0 <= len(s) <= 10^6`
- `1 <= len(pattern) <= 10^5`
### Notes
- The solution should avoid quadratic time in the worst case.
Quick Answer: This question evaluates understanding of string pattern matching and generator/iterator design, testing skills in handling overlapping matches, streaming output, and worst-case time complexity considerations.
Write a function that scans a string from left to right and returns a generator/iterator. The iterator must yield True exactly once for each occurrence of pattern in s. Matches may overlap. For example, in s = "aaaa" with pattern = "aa", the pattern occurs at indices 0, 1, and 2, so the iterator yields True three times. The implementation should avoid quadratic time in the worst case.
Constraints
- 0 <= len(s) <= 10^6
- 1 <= len(pattern) <= 10^5
- Matches may overlap
- The solution should run in O(len(s) + len(pattern)) time
Examples
Input: ("aaaa", "aa")
Expected Output: [True, True, True]
Explanation: The pattern "aa" occurs at starting indices 0, 1, and 2, including overlapping matches.
Input: ("abcdef", "gh")
Expected Output: []
Explanation: The pattern never appears in the string.
Hints
- A naive check at every starting index can become quadratic when the string and pattern contain many repeated characters.
- Consider preprocessing the pattern so that after a mismatch, you know how much of the current partial match can still be reused.