C dynamic programming: longest common subsequence
Dynamic programming solves a problem by combining answers to overlapping subproblems and storing each answer so it is computed once. The longest common subsequence (LCS) of two strings is the longest sequence of characters that appears in both in the same order, though not necessarily next to each other.
C
#include <stdio.h>
#include <string.h>
int main(void) {
const char *a = "AGGTAB";
const char *b = "GXTXAYB";
int n = (int)strlen(a);
int m = (int)strlen(b);
int table[8][9] = {{0}};
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (a[i - 1] == b[j - 1]) {
table[i][j] = table[i - 1][j - 1] + 1;
} else if (table[i - 1][j] >= table[i][j - 1]) {
table[i][j] = table[i - 1][j];
} else {
table[i][j] = table[i][j - 1];
}
}
}
printf("LCS length: %d\n", table[n][m]);
char result[8];
int length = table[n][m];
result[length] = '\0';
int i = n, j = m;
while (i > 0 && j > 0) {
if (a[i - 1] == b[j - 1]) {
result[--length] = a[i - 1];
i--;
j--;
} else if (table[i - 1][j] >= table[i][j - 1]) {
i--;
} else {
j--;
}
}
printf("LCS: %s\n", result);
return 0;
}