Smiley face

Hirschberg Algorithm B(Two-Row, 1975)


Main features
Description

Hirschberg proposed one quadratic space and two linear space algorithms for the longest common subsequence(LCS) of two strings. This algorithm(Algorithm B) is a dynamic programing approch, and solves LCS problem in O(mn) time and in O(m+n) space.

C source code
int Hirschberg_AlgB(char *stringA, char *stringB, int m, int n)
{
   int i, j, **matrix, last, now, lcs = 0;

   matrix = (int**)calloc(2, sizeof(int*));

   for (i = 0; i < 2; i++){
      matrix[i] = (int*)calloc(n + 1, sizeof(int));
   }

   last = 1;
   now = 0;
   /*----------find LCS---------*/
   for (i = 1; i <= m; i++){

      last ^= now;//swap two rows
      now ^= last;
      last ^= now;

      for (j = 1; j <= n; j++){
         if (stringA[i] == stringB[j]){
            matrix[now][j] = matrix[last][j - 1] + 1;
         }
         else{
            if (matrix[now][j - 1] > matrix[last][j])
               matrix[now][j] = matrix[now][j - 1];
            else
               matrix[now][j] = matrix[last][j];
         }
      }
   }
   for (i = 0; i < 2; i++){
      free(matrix[i]);
   }
   free(matrix);
   return lcs;

}

The files
  main.c   lcslib.h   Hirschberg_AlgB.exe


Reference
D. S. Hirschberg, "A linear space algorithm for computing maximal common subsequence," Communications of the ACM, Vol. 24, pp. 664-675, 1975.