1
$\begingroup$

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

$\endgroup$

1 Answer 1

0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.