Improved space-time tradeoffs for approximate full-text indexing with one edit error
Djamal Belazzougui · arXiv (Cornell University) · 2011
In this paper we are interested in indexing texts for substring matching queries with one edit error. That is, given a text $T$ of $n$ characters over an alphabet of size $σ$, we are asked to build a data structure that answers the following query: find all the $occ$ substrings of the text that are at edit distance at most $1$ from a given string $q$ of length $m$. In this paper we show two new results for this problem. The first result, suitable for an unbounded alphabet, uses $O(n\log^εn)$ (where $ε$ is any constant such that $0