title: Levenshtein distance with back tracing in PHP
body: <p>I'm trying to align strings in PHP using Levenshtein distance algorithm. The problem is that my back tracing code does not work properly for all cases. For example when the second array has inserted lines at the beginning. Then the back tracing will only go as far as when i=0.</p>
  
  <p>How to properly implement back tracing for Levenshtein distance?</p>
  
  <p>Levenshtein distance, $s and $t are arrays of strings (rows)</p>
  
  <pre><code>function match_rows($s, $t)
  {
  $m = count($s);
  $n = count($t);
  
  for($i = 0; $i &lt;= $m; $i++) $d[$i][0] = $i;
  for($j = 0; $j &lt;= $n; $j++) $d[0][$j] = $j;
  
  for($i = 1; $i &lt;= $m; $i++)
  {
      for($j = 1; $j &lt;= $n; $j++)
      {
          if($s[$i-1] == $t[$j-1])
          {
              $d[$i][$j] = $d[$i-1][$j-1];
          }
          else
          {
              $d[$i][$j] = min($d[$i-1][$j], $d[$i][$j-1], $d[$i-1][$j-1]) + 1;
          }
      }
  }
  
  // backtrace
  $i = $m;
  $j = $n;
  while($i &gt; 0 &amp;&amp; $j &gt; 0)
  {
      $min = min($d[$i-1][$j], $d[$i][$j-1], $d[$i-1][$j-1]);
  
      switch($min)
      {
          // equal or substitution
          case($d[$i-1][$j-1]):
              if($d[$i][$j] != $d[$i-1][$j-1])
              {
                  // substitution
                  $sub['i'][] = $i;
                  $sub['j'][] = $j;
              }
              $i = $i - 1;
              $j = $j - 1;
              break;
  
          // insertion
          case($d[$i][$j-1]):
              $ins[] = $j;
              $j = $j - 1;
              break;
  
          // deletion
          case($d[$i-1][$j]):
              $del[] = $i;
              $i = $i - 1;
              break;
      }
  }
  </code></pre>