Approximate string matching using a bidirectional index

• DOI: 10.1016/j.tcs.2015.10.043
• Publication Date: 2015-11-04T17:04:31Z
• Authors: Gregory Kucherov; Kamil Salikhov; Dekel Tsur
• Keywords: Formalism (music)

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.