Never re reading the text
A failure link is what turns the prefix function into a fast matcher, the core of the Knuth Morris Pratt approach. When the matcher has aligned several characters of the pattern with the text and then hits a mismatch, a failure link says: instead of moving the text pointer back, fall back the pattern pointer to the next best overlap and continue.
What the link points to
The failure link at a pattern position is exactly the prefix function value there: the length of the longest prefix that also forms a suffix of the matched portion. Following the link means the matcher already knows those leading characters match, so it can keep them and only test what comes next.
Why this is a win
- The text pointer never moves backward, so each text character is examined a bounded number of times.
- Mismatches consult a table lookup rather than restarting.
- Total work becomes proportional to text length plus pattern length, not their product.
Key idea
Failure links let a mismatch reset the pattern pointer to the longest reusable overlap while the text pointer keeps moving forward, so the text is never rescanned and matching stays linear.