Course video 42 of 66

In this lecture we consider algorithms for searching for a substring in a piece of text. We begin with a brute-force algorithm, whose running time is quadratic in the worst case. Next, we consider the ingenious Knuth−Morris−Pratt algorithm whose running time is guaranteed to be linear in the worst case. Then, we introduce the Boyer−Moore algorithm, whose running time is sublinear on typical inputs. Finally, we consider the Rabin−Karp fingerprint algorithm, which uses hashing in a clever way to solve the substring search and related problems.

Princeton University
5 (744 ratings) | 91K Students Enrolled

About Coursera

Courses, Specializations, and Online Degrees taught by top instructors from the world's best universities and educational institutions.

Join a community of 40 million learners from around the world
Earn a skill-based course certificate to apply your knowledge
Gain confidence in your skills and further your career