Week 9: String Algorithms, Approximation (38)

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