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?
j--
from it's originalj = T[j - 1]
to see if it worked, and it still did. $\endgroup$ – user3002473 Nov 20 '18 at 14:46j = T[j - 1]
toj--
is that I proved inductively thatT[i+1] <= T[i] + 1
. $\endgroup$ – user3002473 Nov 20 '18 at 14:47j--
orj = T[j - 1]
is due to my lack of understanding of the conditionW[i] == W[j]
. Do you have any insight into that? $\endgroup$ – user3002473 Nov 20 '18 at 15:11