Knuth–Morris–Pratt algorithm

Definition

Let $P = p_1 \cdots p_m$ and $T = t_1 \cdots t_n$ be strings over a finite alphabet, with $m \ge 1$. The failure function of $P$ is the map $\pi \colon \set{1, \dots, m} \to \set{0, \dots, m - 1}$ such that $\pi(q)$ is the largest $k < q$ with $p_1 \cdots p_k = p_{q - k + 1} \cdots p_q$. The Knuth–Morris–Pratt algorithm is the string-searching algorithm that computes $\pi$ and then runs these steps.

1. Set $q = 0$.
2. For $i = 1, \dots, n$: while $q > 0$ and $p_{q + 1} \ne t_i$, set $q = \pi(q)$.
3. Still for this $i$: if $p_{q + 1} = t_i$, increase $q$ by $1$.
4. Still for this $i$: if $q = m$, report an occurrence at position $i - m + 1$ and set $q = \pi(m)$.

After step 3 for index $i$, $q$ is the length of the longest prefix of $P$ that is a suffix of $t_1 \cdots t_i$.