A new method for approximate indexing and dictionary lookup with one error

摘要

We consider the problem of designing an efficient index for approximate pattern matching. Despite ongoing efforts, this topic is still a challenge in combinatorial pattern matching. We present a new data structure that allows to report all matches in worst-case time O(∣Σ ∣m + occ), which is linear in the pattern length m and the number of occurrences occ for alphabets of constant size ∣Σ∣. Our index uses O(n∣Σ∣ log n) extra space on average and with high probability, where n is the length of the text (indexing) or the number of strings to index (dictionary lookup).