title: Algorithm to find edit distance to all substrings
body: <p>Given 2 strings <code>s</code> and <code>t</code>. I need to find for each substring in <code>s</code> edit distance(Levenshtein distance) to <code>t</code>. Actually I need to know for each <code>i</code> position in <code>s</code> what is the minimum edit distance for all substrings started at position <code>i</code>.</p>
  
  <p>For example:</p>
  
  <pre><code>t = "ab"    
  s = "sdabcb"
  </code></pre>
  
  <p>And I need to get something like:</p>
  
  <p><code>{2,1,0,2,2}</code></p>
  
  <p>Explanation:</p>
  
  <pre><code>1st position:
  distance("ab", "sd") = 4 ( 2*subst )
  distance("ab", "sda") = 3( 2*delete + insert )
  distance("ab", "sdab") = 2 ( 2 * delete)
  distance("ab", "sdabc") = 3 ( 3 * delete)
  distance("ab", "sdabcb") = 4 ( 4 * delete)
  So, minimum is 2
  
  2nd position:
  distance("ab", "da") = 2 (delete + insert)
  distance("ab", "dab") = 1 (delete)
  distance("ab", "dabc") = 2 (2*delete)
  ....
  So, minimum is 1
  
  3th position:
  distance("ab", "ab") = 0
  ...
  minimum is 0
  </code></pre>
  
  <p>and so on.</p>
  
  <p>I can use brute force algorithm to solve this task, of course. But is there faster algorithm? </p>
  
  <p>Thanks for help.</p>