  We study strategies of approximate pattern matching that exploit
bidirectional text indexes, extending and generalizing ideas of Lam et al. We
introduce a formalism, called search schemes, to specify search strategies of
this type, then develop a probabilistic measure for the efficiency of a search
scheme, prove several combinatorial results on efficient search schemes, and
finally, provide experimental computations supporting the superiority of our
strategies.
