Validate optimized matchers against a simple oracle
Implement naive search and KMP, then optionally add a rolling-hash matcher. Give them the same contract: return every matching start index, including overlapping matches, with an explicit empty-pattern policy.
Text "aaaaa", pattern "aaa" -> [0,1,2]
Text "abcabc", pattern "abc" -> [0,3]
Text "abc", pattern "abcd" -> []
Text "abc", pattern "z" -> []
Generate small strings from a tiny alphabet to create repeated prefixes and overlaps. Compare every optimized result with the naive implementation. For hashing, use a deliberately weak modulus to exercise collision verification rather than testing only unlikely-collision inputs.
Acceptance checks
Cover start and end matches, empty inputs, repeated symbols, patterns longer than text, and matches across chunk boundaries for a streaming extension. Verify offsets after any normalization policy, or preserve a mapping back to original positions.
Extension: count comparisons on adversarial repeated-prefix inputs and explain the difference between amortized linear KMP work and naive rescanning.
Check: returning the correct count is insufficient if actual positions are duplicated, omitted, or shifted.