Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
433744 | Theoretical Computer Science | 2016 | 14 Pages |
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Gregory Kucherov, Kamil Salikhov, Dekel Tsur,