Knuth-Morris-Pratt Algorithm (cont)
KMP preprocesses the pattern P[0..m-1] to find matches of its prefixes with itself
- Failure function F(j) defined as
- the size of the largest prefix of P[0..j] that is also a suffix of P[1..j]
- for each position j=0..m-1
- if mismatch occurs at Pj ⇒ advance j to F(j-1)
Example: P = abaaba
| j | 0 | 1 | 2 | 3 | 4 | 5 |
| Pj | a | b | a | a | b | a |
| F(j) | 0 | 0 | 1 | 1 | 2 | 3 |
![[Diagram:Pic/kmp-failure-function.png]](Pic/kmp-failure-function.png)
|
![[prev]](icon/prev.gif){kind=icon}
![[next]](icon/next.gif){kind=icon}