Knuth–Morris–Pratt String Search

Lawrence C. Paulson 📧 with contributions from Christian Zimmerer 📧

November 27, 2023

This is a development version of this entry. It might change over time and is not stable. Please refer to release versions for citations.

Abstract

The naive algorithm to search for a pattern $p$ within a string $a$ compares corresponding characters from left to right, and in case of a mismatch, shifts one position along $a$ and starts again. The worst-case time is $O(|p|\cdot|a|)$. Knuth–Morris–Pratt exploits the knowledge gained from the partial match, never re-comparing characters that matched and thereby achieving linear time. At the first mismatched character, it shifts $p$ as far to the right as safely possible. To do so, it consults a precomputed table, based on the pattern $p$. The KMP algorithm is proved correct.

License

BSD License

Topics

Related publications

Session KnuthMorrisPratt