Improved Space-Time Tradeoffs for Approximate Full-Text Indexing with One Edit Error

摘要

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 sigma, 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(nlog (epsilon) n) (where epsilon is any constant such that 0