29
Knuth-Morris-Pratt Algorithm
(cont)
When a mismatch occurs …
what is the most we can shift the pattern to avoid redundant comparisons?
Answer: the largest
prefix
of
P[0..j]
that is a
suffix
of
P[1..j]
![[Diagram:Pic/kmp-shift.png]](Pic/kmp-shift.png)
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}