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 off line and stored and we focus on recovering the locations with high probability. Using the sparse Fourier transform computation based approach introduced by Pawar and Ramchandran, we show that all such matches can be determined with high probability in sub-linear time. Specifically, if the query length $M = N^mu$ and the number of matches is $L=N^lambda$, as $N rightarrow infty$, we show that  for $lambda < 1-mu$ all the matching positions can be determined with a probability that approaches 1 for $K leq frac{1}{6}M$. More importantly, our scheme has a worst-case computational complexity that is only $Oleft(N^{max(alpha,lambda+1-alpha)} log^2 N right)$ where $alpha=max(mu,1-mu)$ which means we can recover all the matching positions in {it sub-linear} time for $lambda<1-mu$. Further, the number of Fourier transform coefficients that need to be computed, stored and accessed, i.e., the sketching complexity of this algorithm is only $Oleft( N^{max(mu,1-mu)}right)$. Several extensions of the main theme are also discussed.