0
$\begingroup$

I'm trying to learn how the "failure table" is constructed in the Knuth-Morris-Pratt algorithm since it seemed nontrivial to me that you could do it in $O(k)$ time (where $k$ is the length of the pattern, $W$). To be clear, we let the failure table $T$ be a length $k$ array where $T[i]$ is the length of the longest proper prefix of $W$ which is also a suffix of $W[1]\cdots W[i]$.

I was trying to understand it better by reading the following code:

    vector<int> T(pattern.size());
    T[0] = 0;
    int j;
    for (int i = 1; i < pattern.size(); i++) {
        j = T[i - 1];
        // Find largest j s.t. T[:j+1] == T[i-j:i+1]
        while (j > 0 && pattern[j] != pattern[i]) {
            j = T[j - 1];
        }
        T[i] = (pattern[j] == pattern[i]) ? j + 1 : j;
    }
    return T;

The part I'm confused about is why pattern[j] == pattern[i] is enough to guarantee that $T[i] = j + 1$. I was trying to prove this inductively but have had no luck. I've phrased the problem as follows:

Suppose $W[1]\cdots W[T[i - 1]] = W[i - T[i - 1]]\cdots W[i - 1]$. If $W[i] == W[j]$, then is it true that $W[1]\cdots W[j] == W[i - j + 1]\cdots W[i]$?

I can't make any headway with this, nor can I see why it should be true. It still seems like we have to check $W[\ell] = W[i - j + \ell]$ for all $\ell = 1...j$. I can't figure out how to use the inductive hypothesis to prove this result. Do I have to use strong induction (where we assume all prior steps are true and not just the previous step) to prove this?

$\endgroup$
  • $\begingroup$ The code snippet doesn’t look like a correct implementation of KMP. $\endgroup$ – Dmitri Urbanowicz Nov 20 '18 at 14:45
  • $\begingroup$ @DmitriUrbanowicz It passes LeetCode problem 28 (leetcode.com/problems/implement-strstr), however in my own messing around I did change the line j-- from it's original j = T[j - 1] to see if it worked, and it still did. $\endgroup$ – user3002473 Nov 20 '18 at 14:46
  • $\begingroup$ @DmitriUrbanowicz My logic for changing j = T[j - 1] to j-- is that I proved inductively that T[i+1] <= T[i] + 1. $\endgroup$ – user3002473 Nov 20 '18 at 14:47
  • $\begingroup$ Your modification fails to compute the table correctly for this input: "xaxxyxaxxx". $\endgroup$ – Dmitri Urbanowicz Nov 20 '18 at 15:07
  • $\begingroup$ Wow, great counterexample! I knew my change wasn't "proven", I just thought I had heuristic reason to try it, and since it passed all the tests I assumed it worked, but I guess not. Regardless, my inability to prove the correctness of either j-- or j = T[j - 1] is due to my lack of understanding of the condition W[i] == W[j]. Do you have any insight into that? $\endgroup$ – user3002473 Nov 20 '18 at 15:11
1
$\begingroup$

A proper prefix, which is also a suffix of the same string, is usually called border.

The condition you're asking about basically says this:

  1. If $W[1..i-1]$ has a border of length $j$ and $W[j+1] = W[i]$, then $W[1..i]$ has a border of length $j+1$.
  2. If $W[1..i-1]$ has no border of length $j$ such that $W[j+1] = W[i]$, then the length of the maximal border of $W[1..i]$ is $0$.

Both points follow directly from definition of string equality and definition of borders.

What you need to prove is that the while-loop indeed enumerates all possible borders in descending order.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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