Coding questions · Apple

Write a generator for substring pattern matches

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.

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.

Generator for Substring Pattern Matches

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.

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.