Failure array

A failure array (often called a failure function) is an array employed in the course of the KMP algorithm to speed up motif finding in strings.

Specifically, given a string $s$, its failure array $P$ is constructed so that $P[k]$ is equal to the length of the longest substring of $s$ ending at $k$ that isn't a prefix but is equal to some prefix $s[1:i]$, where $i$ must be less than $k$.

For example, given the string "CAGTAAGCAGGGACTG", its failure array is given by $[0 0 0 0 0 0 0 1 2 3 0 0 0 1 0 0]$.