On a mismatch, KMP slides the pattern by the failure link lps[j-1] instead of restarting. The text pointer never moves backward, giving O(n + m).
j = lps[j-1] and keep i fixed.T[i] vs P[j].lps value used to decide how far to slide.i never decreases.j becomes lps[j-1] (not 0) so overlapping matches are still found.ABAB).
The lps panel below the tapes shows the prefix function of the pattern: lps[i] is the length of the
longest proper prefix of P[0..i] that is also a suffix. On a mismatch at pattern index j, KMP reads
lps[j-1] (highlighted gold) and that becomes the new j — the pattern visually slides right by
j - lps[j-1] positions, never restarting at the beginning. This is precisely why the algorithm is linear:
no text character is ever compared as a fresh start twice.
i - j; on a mismatch the offset jumps forward by the failure link instead of by 1.
See junior.md for the walkthrough and professional.md for the proof that the text index never moves backward.
The comparison counter at the top stays linear in the input size — drive k with a long repetitive text to see it never blow up quadratically.