Explain KMP vs Rabin-Karp.

KMP (Knuth-Morris-Pratt) and Rabin-Karp are two popular string-search algorithms: KMP uses a prefix table to achieve guaranteed linear time, while Rabin-Karp applies a rolling hash for fast average-case matching with possible hash collisions.

When to Use

Use KMP for single-pattern searches with predictable performance (e.g., substring searches in compilers). Use Rabin-Karp for multi-pattern or large text matching (e.g., plagiarism or document scanning).

Example

To find “error” in logs, KMP avoids rechecking characters using a prefix table, while Rabin-Karp computes a hash for each substring, quickly spotting potential matches before verification.

Want to master algorithms faster?

Explore Grokking Data Structures & Algorithms for Coding Interviews, Grokking System Design Fundamentals, Grokking the Coding Interview, or practice with Mock Interviews with ex-FAANG engineers.

Why Is It Important

Both algorithms are interview staples—KMP shows your mastery of deterministic string matching, while Rabin-Karp tests your understanding of hashing and probabilistic efficiency.

Interview Tips

Expect questions like “Implement KMP’s LPS array” or “Handle hash collisions in Rabin-Karp.” Focus on explaining space-time trade-offs and real-world usage.

Trade-offs

KMP: O(n+m) guaranteed time but needs extra space for LPS. Rabin-Karp: simpler to code, efficient for multiple patterns, but can degrade to O(nm) with collisions.