String Matching: KMP & Rolling Hash

Advanced · 22 min read · Problem-Solving Patterns, Design, Matrices & Advanced Topics

Find a pattern in O(n + m) with the failure table, and compare substrings in O(1) with hashing.

This is an Advanced lesson, part of Premium. What it covers:

• Why the brute force wastes work
• The failure table (prefix function)
• KMP search
• Rolling hash (Rabin–Karp)
• Which tool when
• Practice ladder
• Interview questions
• Further reading

Previous: Math for Interviews · Next: Range Queries: Fenwick & Segment Trees