Prefix Function

P_k refers to the first k characters of P (the k length prefix of P).

P_m = P

$\begin{eqnarraystar} P &=& \mbox{\tt aababddc}\ P_1 &=& \mbox{\tt a}\ P_2 &=& \mbox{\tt aa}\ P_3 &=& \mbox{\tt aab}\end{eqnarraystar}$ etc.

Given a pattern P[1,m], define the prefix-function $\pi$ :

$\pi[j] = \mbox{max}\{k:k<j\ \mbox{and}\ P_k \sqsupset P_j\}$

Example.

Next: Computing the Prefix Function Up: BOYER-MOORE Previous: Good-Suffix Heuristic