title: Fuzzy Bit Matching
body: <p>I have a very long sequence of bits, called <code>A</code>, and a shorter sequence of bits, <code>x</code>. Two bit sequences of the same length are fuzzy-matched when after aligning them, there are <code>k</code> or fewer mismatched bits. I want to find all such fuzzy occurrences of x within A.</p>
  
  <p>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 <code>O(n_A * n_x)</code>. </p>
  
  <p>I'm told that this can be done in <code>O(n_A * log(n_A))</code> regardless of <code>k</code>. The hint provided is to make use of fast Fourier transform. Remember that for two inputs <img src="https://i.stack.imgur.com/LuAoS.gif" alt="enter image description here"> and <img src="https://i.stack.imgur.com/BdJKE.gif" alt="enter image description here">, convolution produces <img src="https://i.stack.imgur.com/IFsma.gif" alt="enter image description here"> where </p>
  
  <p><img src="https://i.stack.imgur.com/uFxZ1.gif" alt="qqn"></p>
  
  <p>similar to polynomial multiplication. It's not clear to me how to use this hint. Any help would be much appreciated. </p>