Skip to Main content Skip to Navigation
Journal articles

Approximate string matching using a bidirectional index

Abstract : We study strategies of approximate pattern matching that exploit bidirectional text indexes, extending and generalizing ideas of [9]. 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.
Document type :
Journal articles
Complete list of metadata

https://hal-upec-upem.archives-ouvertes.fr/hal-01802942
Contributor : Gregory Kucherov Connect in order to contact the contributor
Submitted on : Tuesday, May 29, 2018 - 11:41:09 PM
Last modification on : Tuesday, October 19, 2021 - 11:26:22 AM

Links full text

Identifiers

Citation

Gregory Kucherov, Kamil Salikhov, Dekel Tsur. Approximate string matching using a bidirectional index. Theoretical Computer Science, Elsevier, 2016, 638, pp.145-158. ⟨10.1016/j.tcs.2015.10.043⟩. ⟨hal-01802942⟩

Share

Metrics

Record views

143