Brute-Force Substring Search

Course video 40 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.

Sobre o Coursera

Cursos, especializações e graduações on-line, ministradas pelos melhores instrutores das melhores universidades e instituições de ensino.

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