Bad-Character Heuristic Algorithm

Compute the $\lambda$ mapping.


\begin{algorithm} {Compute-Last-Occurrence-Function}{P,m,\Sigma} \begin{FOR} {\... ...OR}\ \begin{FOR} {j \= 1 \TO m} \lambda[P[j]] \= j \end{FOR} \end{algorithm}

Running time is $O(\vert\Sigma\vert+m)$.

next up previous
Next: When does it help? Up: BOYER-MOORE Previous: Bad-Character Heuristic Analysis