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