Knuth-Morris-Pratt Algorithm
The Knuth-Morris-Pratt algorithm …
- compares the pattern to the text left-to-right
- but shifts the pattern more intelligently than the naive algorithm
Reminder:
- Q is a prefix of P … P = Qω, for some ω∈Σ*
- Q is a suffix of P … P = ωQ, for some ω∈Σ*
|