title: Fastest way to find minimal Hamming distance to any substring?
body: <p>Given a long string <code>L</code> and a shorter string <code>S</code> (the constraint is that <code>L</code>.length must be >= <code>S</code>.length), I want to find the minimum Hamming distance between <code>S</code> and any substring of <code>L</code> with length equal to <code>S</code>.length.  Let's call the function for this <code>minHamming()</code>.  For example, </p>
  
  <p><code>minHamming(ABCDEFGHIJ, CDEFGG) == 1</code>.</p>
  
  <p><code>minHamming(ABCDEFGHIJ, BCDGHI) == 3</code>.</p>
  
  <p>Doing this the obvious way (enumerating every substring of L) requires O(<code>S</code>.length * <code>L</code>.length) time.  Is there any clever way to do this in sublinear time?  I search the same <code>L</code> with several different <code>S</code> strings, so doing some complicated preprocessing to <code>L</code> once is acceptable.</p>
  
  <p>Edit:  The modified Boyer-Moore would be a good idea, except that my alphabet is only 4 letters (DNA).</p>