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+\log \log n+\text{\#}\text{matches})$ time (for constant k). The space complexity of the index is $O(n^{1+?})$ for any constant $?>0$.