﻿ Hirschberg B

# Hirschberg Algorithm B(Two-Row, 1975)

Main features
• require only row i-1 of matrix L
• searching phase in O(mn) time complexity
• searching phase in O(m+n) space complexity
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.