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

Question

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?

Answer 1

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.