[prev] 38 [next]

Knuth-Morris-Pratt Algorithm (cont)

Analysis of failure function computation:
  • At each iteration of the while-loop, either
    • i increases by one, or
    • the "shift amount" i-j increases by at least one   (remember that always F(j-1)<j)
  • Hence, there are no more than 2·m iterations of the while-loop
⇒  failure function can be computed in O(m) time