 Prefix function

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.