# Confused about constructing the “failure table” in Knuth-Morris-Pratt algorithm

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?

• The code snippet doesn’t look like a correct implementation of KMP. – Dmitri Urbanowicz Nov 20 '18 at 14:45
• @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. – user3002473 Nov 20 '18 at 14:46
• @DmitriUrbanowicz My logic for changing j = T[j - 1] to j-- is that I proved inductively that T[i+1] <= T[i] + 1. – user3002473 Nov 20 '18 at 14:47
• Your modification fails to compute the table correctly for this input: "xaxxyxaxxx". – Dmitri Urbanowicz Nov 20 '18 at 15:07
• 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? – user3002473 Nov 20 '18 at 15:11

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$$.