Skip to Main content Skip to Navigation
Conference papers

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 [5]. We introduce a formalism, called search schemes, to specify search strate-gies 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 :
Conference papers
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download
Contributor : Admin Ligm Connect in order to contact the contributor
Submitted on : Sunday, November 23, 2014 - 9:39:45 AM
Last modification on : Saturday, January 15, 2022 - 3:56:11 AM
Long-term archiving on: : Tuesday, February 24, 2015 - 10:06:39 AM


Files produced by the author(s)



Gregory Kucherov, Kamil Salikhov, Dekel Tsur. Approximate String Matching Using a Bidirectional Index. CPM 2014, Jun 2014, Moscow, Russia. pp.222-231, ⟨10.1007/978-3-319-07566-2_23⟩. ⟨hal-01086206⟩



Record views


Files downloads