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.
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;
}