Longest Common Subsequence

Dynamic Programming O(m · n) O(m · n)

Finds the longest subsequence shared by two strings by building a 2-D table of subproblem answers.

ε	ε	G	A	C
ε	·	·	·	·
A	·	·	·	·
G	·	·	·	·
C	·	·	·	·
A	·	·	·	·
T	·	·	·	·

String AString B

1/49

Row 0, col 0: an empty string has no subsequence.

Invariantdp[i][j] is the answer for the first i of a and the first j of b — already final, never revisited.

computingreads fromfilled

lcs.c

int max(int a, int b) { return a > b ? a : b; }
 
int lcs(const char *a, const char *b) {
    int m = strlen(a), n = strlen(b);
    int dp[m + 1][n + 1];
 
    for (int i = 0; i <= m; i++) {
        for (int j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                dp[i][j] = 0;
            else if (a[i - 1] == b[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }
    return dp[m][n];
}

How Longest Common Subsequence works

dp[i][j] = LCS length of the first i chars of A and first j of B. Matching characters extend the diagonal by 1; otherwise inherit the better of dropping a character from either string.

When to use it

Diff tools, DNA sequence alignment, plagiarism detection — any 'how similar are two sequences' question.