Prefix function
= Prefix function
{title2=$\pi$}
For a string $s$, the value $\pi_i$ is the length of the longest proper prefix of $s_0\cdots s_i$ that is also its suffix. Repeatedly following these lengths lists all proper <borders of a string>; this is the failure-link information used by the <Knuth-Morris-Pratt algorithm>.