Write a generator for substring pattern matches

Q: 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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

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.