C dynamic programming: longest common subsequence

Fill a table of subproblem answers to find the longest sequence that two strings share.

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

Output

LCS length: 4
LCS: GTAB

Explanation

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.

Let L[i][j] be the LCS length of the first i characters of one string and the first j characters of the other. If the last characters match, L[i][j] = L[i−1][j−1] + 1. Otherwise it is the larger of L[i−1][j] and L[i][j−1]. The first row and column are zero. The bottom-right entry is the answer, and walking back through the table recovers the subsequence itself.

Explore the dry run

Guided walkthroughReady

1#include <stdio.h>

2#include <string.h>

4int main(void) {

5 const char *a = "AGGTAB";

6 const char *b = "GXTXAYB";

7 int n = (int)strlen(a);

8 int m = (int)strlen(b);

9 int table[8][9] = {{0}};

11 for (int i = 1; i <= n; i++) {

12 for (int j = 1; j <= m; j++) {

13 if (a[i - 1] == b[j - 1]) {

14 table[i][j] = table[i - 1][j - 1] + 1;

15 } else if (table[i - 1][j] >= table[i][j - 1]) {

16 table[i][j] = table[i - 1][j];

17 } else {

18 table[i][j] = table[i][j - 1];

19 }

20 }

21 }

22 printf("LCS length: %d\n", table[n][m]);

24 char result[8];

25 int length = table[n][m];

26 result[length] = '\0';

27 int i = n, j = m;

28 while (i > 0 && j > 0) {

29 if (a[i - 1] == b[j - 1]) {

30 result[--length] = a[i - 1];

31 i--;

32 j--;

33 } else if (table[i - 1][j] >= table[i][j - 1]) {

34 i--;

35 } else {

36 j--;

37 }

38 }

39 printf("LCS: %s\n", result);

40 return 0;

41}

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
One extra row and column of zeros for the empty prefixes.	`—`	—
A matching pair extends the best subsequence of the shorter prefixes by one.	`—`	—
No match: take the better of dropping the last character of either string.	`—`	—
The bottom-right entry holds the answer for the whole strings.	`—`	LCS length: 4
Walking back through the table, each diagonal step contributes a matching character, filled in from the end.	`—`	LCS length: 4
G, T, A, and B appear in both strings in this order.	`—`	LCS length: 4 LCS: GTAB

Cost and common mistakes

O(n·m) time and O(n·m) space; the length alone needs only O(min(n, m)) space.

Mixing up the indexes is the usual bug. The table index i corresponds to the character a[i - 1].
A subsequence need not be contiguous. A substring must be, which is a different problem.
When the two choices are equal there can be several LCSs of the same length. The tie-break decides which one is returned.

Try it yourself

What is the LCS length of ABC and DEF?

Reveal answer and reasoning

0, because the strings have no character in common.

C dynamic programming: longest common subsequence

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading