function DPA(s1, s2)
 { var m = new Array();
   var i, j;
   for(i=0; i < s1.length + 1; i++) m[i] = new Array(); // i.e. 2-D array

   m[0][0] = 0; // boundary conditions

   for(j=1; j <= s2.length; j++)
      m[0][j] = m[0][j-1]-0 + 1; // boundary conditions

   for(i=1; i <= s1.length; i++)                            // outer loop
    { m[i][0] = m[i-1][0]-0 + 1; // boundary conditions

      for(j=1; j <= s2.length; j++)                         // inner loop
       { var diag = m[i-1][j-1];
         if( s1.charAt(i-1) != s2.charAt(j-1) ) diag++;

         m[i][j] = Math.min( diag,               // match or change
                   Math.min( m[i-1][j]-0 + 1,    // deletion
                             m[i][j-1]-0 + 1 ) ) // insertion
       }//for j
    }//for i

   var d = m[s1.length][s2.length];

   var tb = traceBack('', '', '', m, s1.length, s2.length, s1, s2);
   return new Array( d, tb[0], tb[1], tb[2] );
 }//DPA


function traceBack( row1,row2,row3, m, i,j, s1,s2 )
// recover the alignment of s1 and s2, e.g.,
//   s1, row1: appropriate m-eaning  -> i
//       row2: |||||...|||||-...|||
//   s2, row3: approximate matching  -> j
 { if(i > 0 && j > 0)
    { var diag = m[i-1][j-1], matchCh = '|', mismCh = '.', indelCh = '-';
      var diagCh = matchCh;

      if( s1.charAt(i-1) != s2.charAt(j-1) )
       { diag++;  diagCh = mismCh; }

      if( m[i][j] == diag )   // change or match
        return traceBack(s1.charAt(i-1)+row1, diagCh+row2, s2.charAt(j-1)+row3,
                         m, i-1, j-1, s1, s2);
      else if( m[i][j] == m[i-1][j]-0 + 1 )   // delete
        return traceBack(s1.charAt(i-1)+row1, indelCh+row2, '-'+row3,
                         m, i-1, j, s1, s2);
      else   // insertion
        return traceBack('-'+row1, indelCh+row2, s2.charAt(j-1)+row3,
                         m, i, j-1, s1, s2);
    } // assert i==0 | j==0
   else if(i > 0)
      return traceBack(s1.charAt(i-1)+row1, indelCh+row2, '-'+row3,
                       m, i-1, j, s1, s2);
   else if(j > 0)
      return traceBack('-'+row1, indelCh+row2, s2.charAt(j-1)+row3,
                       m, i, j-1, s1, s2);
   else // i==0 and j==0
      return new Array( row1, row2, row3 );
 }//traceBack


// Lloyd Allison, http://www.allisons.org/ll/