 Failure link

A transition to a shorter suffix match after an attempted extension fails. In a Knuth-Morris-Pratt automaton, the prefix function determines the next shorter matching prefix.