<p>Computing the Levenshtein distances for a sliding window boils down to computing the distances between several pairs of vertices in an acyclic directed <em>planar</em> graph that looks like this one (capital letters denote the pairs).</p>

<pre><code>   h a y s t a c k

n  A-B-C-D-E-F-*-*
   |\|\|\|\|\|\|\|
e  *-*-*-*-*-*-*-*
   |\|\|\|\|\|\|\|
e  *-*-A-B-C-D-E-F
</code></pre>

<p>The horizontal and vertical arcs have cost 1; the diagonal arcs have cost 0 if the corresponding letters match or 1 otherwise.</p>

<p>Since all of the paired vertices lie on the infinite face, Klein's or <a href="http://arxiv.org/abs/1202.0314" rel="nofollow">Cabello-Chambers's</a> multiple-source shortest paths algorithm can be used to compute the needed distances in time O(m n log (m n)).</p>

<p>To shave the final log (and practically speaking, it's much worse than for, e.g., Dijkstra's algorithm), you might look in Alexander Tiskin's manuscript <a href="http://arxiv.org/abs/0707.3619" rel="nofollow">Semi-local string comparison: Algorithmic techniques and applications</a>, which treats problems similar to this one if not this one itself. (Probably that should be my primary answer, but I haven't read it and know the multiple-source shortest path techniques a lot better.)</p>

<p><sub><sup>It's also possible that, with some additional logic to handle the unidirectional edges, my <a href="http://www.davideisenstat.com/cv/EisenstatK13.pdf" rel="nofollow">multiple-source shortest path algorithm with Klein</a> could be made to achieve O(m n).</sup></sub></p>
Semi-local Levenshtein distance
<p>[Reposted from <a href="https://cs.stackexchange.com/questions/12986/sliding-window-edit-distance">https://cs.stackexchange.com/questions/12986/sliding-window-edit-distance</a> ]</p>

<p>If you have a long string of length n and a shorter string of length m, what is a suitable recurrence to let you compute all n-m+1 <a href="http://en.wikipedia.org/wiki/Levenshtein_distance" rel="nofollow noreferrer">Levenshtein distances</a> between the shorter string and all substrings of the longer string of length m?</p>

<p>Can it in fact be done in O(nm) time?</p>