# Knuth–Morris–Pratt algorithm - Determine the next position of the proper prefix of the pattern string

When I learn Knuth–Morris–Pratt algorithm, I got a function f from the book Fundamentals of Data Structures in C.

If p="p0 p1 ...p(n-1)" is a pattern, then its failure function, f, is defiened as:

f(j)= largest i<j such that p0 p1 ... p(i) = p(j-i) p(j-i+1) ... p(j), if such an i>=0 exists
f(j)= -1, otherwise.


Here's its restatement:

f(j)= -1, if j=0
f(j)= f_m(j-1)+1, where m is the least integer k for which p[f_k(j-1) + 1]=p[j]
f(j)= -1, if there is no k satisfying the above
(note that f_1(j)=f(j) and f_m(j)=f(f_m-1(j)))


And I got a problem about the second line of the restatement of f.

Let me introduce my pseudocode conventions:

1. All strings are 0-based which means they start from position 0.
2. Denote a string as str[0:m] which means the string contains characters: str[0], str1, ..., str[m].
3. The substring of str could be str[0:0], str[0:1], ...,etc.

Question: If we know the value of f(j-1) and we are determining the value of f(j) Why is the next potential position of f(j) equals to f(f(j-1))+1 after checking p[f(j-1) + 1] != p[j]?

Here are my thoughts:

1. A proper prefix of a string is a prefix that is not equal to the string itself. A proper suffix of a string is a suffix that is not equal to the string itself. These imply that 0 < f(k).

2. pat[0:k] extends a character from pat[0:k-1].

(pat[0:k] = pat[0:k-1] + pat[k])

It implies that the longest proper prefix which is also a proper suffix of pat[0:k] at most extends a character from the one of pat[0:k-1]. ( f(k)<=f(k-1)+1 )

3. p[f(j-1) + 1] != p[j] It implies that pat[0:f(j-1) + 1] is not the longest proper prefix which is also a proper suffix of pat[0:k]. (f(k)<=f(k-1))

4. By the previous discussion, 0 < f(k) <= f(k-1).

Then, why does the next potential position of f(j) is f(f(j-1))+1, and we don't need to check the positions of f(k) in order of f(k-1), f(k-1)-1, f(k-1)-2, ..., 0 ?

I've studied the following source:

Fundamentals of Data Structures in C

Prefix function. Knuth–Morris–Pratt algorithm - Algorithms for Competitive Programming

Knuth–Morris–Pratt algorithm - wiki

That's a reasonable question. Let's say that string $$t$$ is a border of string $$s$$ if $$t$$ is a proper prefix of $$s$$ and a proper suffix of $$s$$ at the same time. Then $$f(\cdot)$$ is a function which returns maximum length of border for every prefix of $$s$$.
It is easy to see that a border of a border of $$s$$ is a border of $$s$$. However there is a kind of inverse of this statement: if $$u$$ and $$v$$ are borders of $$s$$ and $$|u| < |v|$$, then $$u$$ is a border of $$v$$. Let's prove it: $$u = u[0 : |u| - 1] = s[0 : |u| - 1] = v[0 : |u| - 1],$$ since $$s[0 : |v| - 1] = v[0 : |v| - 1]$$, and $$u = u[|u| - |u| : |u| - 1] = s[|s| - |u| : |s| - 1] = v[|v| - |u| : |v| - 1],$$ since $$s[|s| - |v| : |s| - 1] = v[|v| - |v| : |v| - 1]$$. So $$u$$ is both prefix and suffix of $$v$$. That's why iterating a function which returns the longest border of a string we consider all borders of this string and nothing else.
To finish the proof of the correctness we note that if $$t$$ is a border of prefix $$s[0 : i]$$ and $$|t| > 0$$, then $$t[0 : |t| - 2]$$ is a border of $$s[0 : i - 1]$$ (not necessarily the longest one). That's why doing step from $$s[0 : i - 1]$$ to $$s[0 : i]$$ and searching for the longest border of $$s[0 : i]$$ we need to consider only borders of $$s[0 : i - 1]$$ trying to append a character to them.