### 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

- Computer science/Algorithms

### Related publications

- Knuth, D. E., Morris, Jr., J. H., & Pratt, V. R. (1977). Fast Pattern Matching in Strings. SIAM Journal on Computing, 6(2), 323–350. https://doi.org/10.1137/0206024
- Wikipedia

### Session KnuthMorrisPratt

- KnuthMorrisPratt

### Depends on

- Collections Framework

## Cite

×

KnuthMorrisPratt-AFP

    @article{KnuthMorrisPratt-AFP,
      author  = {Lawrence C. Paulson},
      title   = {Knuth–Morris–Pratt String Search},
      journal = {Archive of Formal Proofs},
      month   = {November},
      year    = {2023},
      note    = {\url{https://isa-afp.org/entries/KnuthMorrisPratt.html},
                 Formal proof development},
      ISSN    = {2150-914x},
    }

Download

## Download

× Download latest