Why can the KMP failure function be computed in O(n) time?

Question

Wikipedia claims that the failure function table can be computed in O(n) time.

Let's look at its `canonical' implementation (in C++):

vector<int> prefix_function (string s) {
    int n = (int) s.length();
    vector<int> pi (n);
    for (int i=1; i<n; ++i) {
        int j = pi[i-1];
        while (j > 0 && s[i] != s[j])
            j = pi[j-1];
        if (s[i] == s[j])  ++j;
        pi[i] = j;
    }
    return pi;
}

Why does it work in O(n) time, even if there is an inner while-loop? I'm not really strong at the analysis of algorithms, so may somebody explain it?

Answer 1

This line: if (s[i] == s[j]) ++j; is executed at most O(n) times. It caused increase in the value of p[i]. Note that p[i] starts at same value as p[i-1].

Now this line: j = pi[j-1]; causes decrease of p[i] by at least one. And since it was increased at most O(n) times (we count also increases and decreases on previous values), it cannot be decreased more than O(n) times. So it as also executed at most O(n) times.

Thus the whole time complexity is O(n).