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