Notation

Let P be a string in $\Sigma^*$ .

P[i..j]: Array range notation character i to j inclusive indexed from 1 to length of string.

|P| denotes the length of string P.

AB is the concatenation of strings A and B.

$Q \sqsubset R$ : the string Q is a prefix of R. R = QS for some S.

$\begin{eqnarraystar} Q &=& \mbox{\tt abc}\ R &=& \mbox{\tt abcbbca} \ S &=& \mbox{\tt bbca} \end{eqnarraystar}$

$Q \sqsupset R$ : the string Q is a suffix of R. R = SQ for some S.

$\begin{eqnarraystar} Q &=& \mbox{\tt bca}\ R &=& \mbox{\tt abcbbca} \ S &=& \mbox{\tt abcb}\end{eqnarraystar}$

Next: The String Matching Problem Up: STRING MATCHING Previous: Alphabets