﻿ Hirschberg A

Main features
• Algorithm A produces as output the matrix L corresponds to our notation of maximum length possible of any common subsequence
• searching phase in O(mn) time complexity
• searching phase in O(mn) 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 A) is a dynamic programing approch, and solves LCS problem in O(mn) time and in O(mn) space.

C source code
```int Hirschberg_AlgA(char *stringA, char *stringB, int m, int n)
{
int i, j, **matrix, lcs = 0;
matrix = (int**)calloc(m + 1, sizeof(int*));
for (i = 0; i < m + 1; i++){
matrix[i] = (int*)calloc(n + 1, sizeof(int));
}
/*----------find LCS---------*/
for (i = 1; i <= m; i++){
for (j = 1; j <= n; j++){
if (stringA[i] == stringB[j]){
matrix[i][j] = matrix[i - 1][j - 1] + 1;
}
else{
if (matrix[i][j - 1] > matrix[i - 1][j])
matrix[i][j] = matrix[i][j - 1];
else
matrix[i][j] = matrix[i - 1][j];
}
}
}
lcs=matrix[m][n];
for (i = 0; i < m + 2; i++){
free(matrix[i]);
}
free(matrix);
return lcs;
}

```
The files
main.c   lcslib.h   Hirschberg_AlgA.exe

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