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"