function fwdDPA(s1,p1,p2, s2,q1,q2, m)
// DPA on s1[p1..p2) and s2[q1..q2)
 { var i, j;

   m[p1%2][q1] = 0.0; // boundary conditions
   for(j=q1+1; j <= q2; j++)
      m[p1%2][j] = m[p1%2][j-1] + 1;

   for(i=p1+1; i <= p2; i++)     // outer loop
    { m[i%2][q1] = m[(i-1)%2][q1] + 1; // boundary conditions

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

         m[i%2][j] = Math.min( diag,
                     Math.min( m[(i-1)%2][j]+1,
                               m[i%2][j-1]+1 ) )
       }//for j
    }//for i
 }//fwdDPA


function revDPA(s1,p1,p2, s2,q1,q2, m)
// DPA on reverse(s1[p1..p2)) and reverse(s2[q1..q2))
 { var i, j;

   m[p2%2][q2] = 0.0; // boundary conditions
   for(j=q2-1; j >= q1; j--)
      m[p2%2][j] = m[p2%2][j+1]+1;

   for(i=p2-1; i >= p1; i--)
    { m[i%2][q2] = m[(i+1)%2][q2] + 1;

      for(j=q2-1; j >= q1; j--)
       { var diag = m[(i+1)%2][j+1];
         if( s1.charAt(i) != s2.charAt(j) ) diag += 1;

         m[i%2][j] = Math.min( diag,
                     Math.min( m[(i+1)%2][j]+1,
                               m[i%2][j+1]+1 ) );
       }
    }
 }//revDPA


function DandC_alg(fwd,rev, s1,p1,p2, s2,q1,q2, Level)
// align sequence s1[p1..p2) with sequence s2[q1..q2)
 { var mid, i, row = new Array('', '', '');

   for(i=1; i < Level; i++)      // for tracing purposes only
      document.DPA_DandC_form.trace.value+='   ';
   document.DPA_DandC_form.trace.value
    += 's1['+p1+'..'+(p2-1)+'] : s2['+q1+'..'+(q2-1)+']\n';//trace

   if( p2 <= p1 )      // s1 is empty string
      for(i=q1; i < q2; i++)
       { row[0] += '-'; row[1] += '-'; row[2] += s2.charAt(i); }

   else if( q2 <= q1 ) // s2 is empty string
      for(i=p1; i < p2; i++)
       { row[0] += s1.charAt(i); row[1] += '-'; row[2] += '-'; }

   else if( p2-1 == p1 ) // s1 is one character and s2 is not empty
    { var ch = s1.charAt(p1), memo = q1;
      for(i=q1+1; i < q2; i++) if(s2.charAt(i) == ch) memo=i;
      for(i=q1; i < q2; i++)
       { if(i == memo)
          { row[0] += ch;
            if(s2.charAt(i) == ch) row[1] += '|'; else row[1] += '.';
          }
         else { row[0] += '-'; row[1] += '-'; }
         row[2] += s2.charAt(i);
       }
    } // a b [l=2] mid=1, a b c [l=3] mid=1, a b c d [l=4] mid=2

   else // p2>p1+1, s1 has 2+ chars & s2 is not empty, divide s1 & conquer
    { var mid = Math.floor((p1+p2)/2);
      fwdDPA(s1, p1, mid, s2, q1, q2, fwd);
      revDPA(s1, mid, p2, s2, q1, q2, rev);
      var s2mid=q1, best=Number.MAX_VALUE;
      for(i=q1; i<=q2; i++)  // look for cheapest corresponding split of s2
       { var sum = fwd[mid%2][i]+rev[mid%2][i];
         if( sum < best ) { best=sum; s2mid=i; }
       }
      var r1 = DandC_alg(fwd,rev, s1,p1,mid, s2,q1,s2mid, Level+1);
      var r2 = DandC_alg(fwd,rev, s1,mid,p2, s2,s2mid,q2, Level+1);
      row[0] = r1[0]+r2[0]; row[1] = r1[1]+r2[1]; row[2] = r1[2]+r2[2];
    }
   return row;
 }//DandC_alg


function DPA_DandC(s1, s2)
 { var fwd = new Array(), rev = new Array();
       fwd[0] = new Array(); fwd[1] = new Array();  // i.e. linear...
       rev[0] = new Array(); rev[1] = new Array();  // ...space, O(|s2|).

   // align s1[0,|s1|) to s2[0,|s|)
   return DandC_alg(fwd,rev, s1,0,s1.length, s2,0,s2.length, 1);
 }//DPA_DandC


// Divide and Conquer Edit-Distance in linear-space, after Hirschberg.
// Lloyd Allison, http://www.allisons.org/ll/                    2007.
//
// Note, the JavaScript will likely be slower than O(|s1|*|s2|)-time
// because of (i) the use of string concatenation in constructing the
// alignment, and (ii) the trace which shows the algorithm working.
// In production code, the former would be replaced by O(1) operations,
// and the latter would be deleted.