Fast index for approximate string matching

We present an index that stores a text of length n such that given a pattern of length m, all the substrings of the text that are within Hamming distance (or edit distance) at most k   from the pattern are reported in O(m+loglogn+#matches) time (for constant k  ). The space complexity of the index is O(n1+ϵ)O(n1+ϵ) for any constant ϵ>0ϵ>0.