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 distance of K from the query. We assume that sketches of the original signal can be computed offline and stored. Using a sparse Fourier transform computation based approach, we show that all such matches can be determined with high probability in sub-linear time.