The Suffix-Function

Given a pattern P[1..m], define the suffix-function $\sigma$ such that $\sigma(x)$ is the length of the longest prefix of P that is also a suffix of x:

$\sigma(x) =\ {\rm max}\ \{k:P_k \sqsupset x\}$

\begin{eqnarraystar} P &=& \mbox{\tt abaabc}\ P_1 &=& \mbox{\tt a}\ P_2 &=& \m... ...\mbox{\tt abaa}\ \sigma(\mbox{\tt abbaba}) &=& \mbox{\tt aba}\end{eqnarraystar}

next up previous
Next: String-Matching Automata Up: STRING MATCHING WITH FINITE Previous: Example