# Longest Common Subsequence in C

This Longest Common Subsequence (LCS) algorithm is a classic dynamic programming table-filling algorithm.

static size_t longest_common_subsequence_internal(const char *str1, const char *str2, matrix **mat)
{
int i, j;
const size_t alen = strlen(str1);
const size_t blen = strlen(str2);
*mat = matrix_create(alen, blen);
if (*mat == NULL) {
return 0;
}
for (i = alen - 1; i >= 0; i--) {
for (j = blen - 1; j >= 0; j--) {
if (str1[i] == str2[j]) {
matrix_set(*mat, i, j, 1 + matrix_get(*mat, i + 1, j + 1));
}
else {
matrix_set(*mat, i, j, max(matrix_get(*mat, i + 1, j), matrix_get(*mat, i, j + 1)));
}
}
}
return matrix_get(*mat, 0, 0);
}

size_t longest_common_subsequence_length(const char *str1, const char *str2)
{
matrix *mat;
size_t result = longest_common_subsequence_internal(str1, str2, &mat);
matrix_delete(mat);
return result;
}

char *longest_common_subsequence(const char *str1, const char *str2)
{
matrix *mat;
size_t lcs_len = longest_common_subsequence_internal(str1, str2, &mat);
unsigned int i = 0;
unsigned int j = 0;
unsigned int k = 0;
const unsigned int alen = strlen(str1);
const unsigned int blen = strlen(str2);
char *lcs = malloc(lcs_len + 1);
while (i < alen && j < blen) {
if (str1[i] == str2[j]) {
lcs[k] = str1[i];
i++;
j++;
k++;
}
else if (matrix_get(mat, i + 1, j) >= matrix_get(mat, i ,j + 1)) {
i++;
}
else {
j++;
}
}
lcs[k] = '\0';
matrix_delete(mat);
return lcs;
}


Example program:

int main(void)
{
char str1[] = "pAqBrCs";
char str2[] = "wAxByCz";
char *lcs;
lcs = longest_common_subsequence(str1, str2);
printf("The longest common subsequence is \"%s\"\n", lcs);
free(lcs);
return 0;
}

The longest common subsequence is "ABC"