Solution videos are here - Watch walkthroughs for selected problems. Check them out

⚡ Build the skills to land top-paying quant jobs. Offer ends in 17d 22h 20m 11s17 days 22 hours 20 minutes 11 seconds.

Algorithms - Strings · 4:11

Brute-force String Matching

The simplest way to find a pattern in a text tries every start and compares letter by letter. We slide aab across aaaaaaaab and watch every alignment do the maximum work, derive the O(nm) worst case, measure a billion comparisons against near-linear random text on a Mac, show that std::string::find and the Horspool searcher have bad inputs too, expose hidden costs like substr in a loop, and pin down what brute force forgets at every mismatch.

You will learn

Implement brute-force matching with the correct loop bound (i + m <= n) and an early exit, counting overlapping occurrences
Derive the worst case (n - m + 1) * m and construct inputs that reach it
Recognise that std::string::find, Horspool and substr-based loops all have quadratic worst cases or hidden costs
Explain what information brute force discards at a mismatch, motivating hashing and KMP

Chapters

PreviousTries NextString Hashing