Fuzzy Bit Matching

Question

I have a very long sequence of bits, called A, and a shorter sequence of bits, x. Two bit sequences of the same length are fuzzy-matched when after aligning them, there are k or fewer mismatched bits. I want to find all such fuzzy occurrences of x within A.

So far, I've tried the naive approach. Loop through A, then for each bit, loop through the length of x, count the number of mismatched bits starting at that position in A, and if it doesn't exceed k, report that position. This algorithm is not efficient. If A has n_A bits, and x has n_x bits, the running time is O(n_A * n_x).

I'm told that this can be done in O(n_A * log(n_A)) regardless of k. The hint provided is to make use of fast Fourier transform. Remember that for two inputs and , convolution produces where

similar to polynomial multiplication. It's not clear to me how to use this hint. Any help would be much appreciated.

Answer 1

Reverse x, replace each bit b by (-1)**b, and convolve. I'll let you explain on your homework what to do next.