Sub-string/Pattern Matching in Sub-linear Time Using a Sparse Fourier Transform Approach

We consider the problem of querying a string (or, a database) of length N bits to determine all the locations where a substring (query) of length M appears either exactly or is within a Hamming dis