[prev] 34 [next]

Knuth-Morris-Pratt Algorithm (cont)

Analysis of Knuth-Morris-Pratt algorithm:
  • Failure function can be computed in O(m) time   (→ next slide)
  • At each iteration of the while-loop, either
    • i increases by one, or
    • the pattern is shifted ≥1 to the right   ("shift amount" i-j increases since always F(j-1)<j)
    ⇒ i can be incremented at most n times, pattern can be shifted at most n times
    ⇒ there are no more than 2·n iterations of the while-loop
⇒  KMP's algorithm runs in optimal time O(m+n)