String Algorithms: KMP, Boyer-Moore, Rabin-Karp, Aho-Corasick and the Regex That Broke the Internet

Deep End Era. Engineering with Sankalp · Oct 28, 2026 · 52m

A fictional malware scanning team watches its cluster choke on one bad signature. Along the way: worked examples of a KMP table and a Horspool search by ear, why longer patterns search faster, why GNU grep is fast, and when not to write your own string matcher.

Chapters

00:00:00 Cold open: a million signatures, a billion emails

00:02:29 The naive search, and why it hurts

00:04:28 Knuth, Morris and Pratt: never look back

00:07:45 A worked example: building the KMP table by ear

00:09:58 The fastest search is the one in your standard library

00:11:16 Boyer and Moore: look from the end, and skip…