Longest Common Subsequence (LCS)

LCS compares two sequences while allowing characters to be skipped in either one. A common subsequence preserves both orders; a substring must be contiguous and is a different problem. Prefix DP merges repeated choices about how much of each string has been processed. The program computes the length and reconstructs one common subsequence, using the full table for backtracking.

Prerequisites: Two-Dimensional DP; reconstruction; string indexing. Related existing lessons: String Dynamic Programming.

Build the idea

1. Recognize the repeated subproblems

   Brute force can enumerate subsequences of one string and test them in the other, but there are exponentially many. Repeated recursive decisions to skip from either string lead to the same pair of remaining prefixes. Length bounds of 2000 suggest about four million prefix pairs, making O(nm) time and a full integer table practical.

2. Define the state

   dp[i][j] is LCS length of the first i characters of a and the first j of b. Indices refer to prefix lengths, so the newest characters are a[i−1], b[j−1]. The state is sufficient because earlier matched choices affect neither the unprocessed prefix order nor the objective beyond their achieved length.

3. Derive the transition

   If last characters match, extend an optimal common subsequence of the shorter prefixes:dp[i−1][j−1]+1. An optimum can use this matching last pair without losing length. If they differ, a common subsequence cannot use both as its last matched pair, so at least one must be skipped; take max(dp[i−1][j], dp[i][j−1]). Unlike substring DP, a mismatch does not reset the answer to zero.

   $$\mathrm{dp}\left[i\right]\left[j\right]=\max \left(\mathrm{dp}\right[i-1\left]\right[j],\mathrm{dp}[i\left]\right[j-1\left]\right)\mathrm{when}a[i-1]\ne b[j-1]$$

4. Base cases and computation order

   Empty-prefix row and column are zero. Fill i, j increasing, so above, left, diagonal dependencies are ready. Backtrack from (n, m): equal characters are appended while moving diagonally; on a mismatch move to a predecessor with the same optimal value, preferring upward ties here. Reverse collected characters. Two input lines allow either string to be empty.

5. Correctness and invariant

   The last-character cases cover all subsequences and can construct an attaining answer, proving correctness by induction on i+j. Backtracking follows equal-value skip transitions or a one-character matching transition, so it preserves a valid optimum while decreasing indices. Storing only rolling rows computes the length but loses these direct table comparisons; another reconstruction method would be necessary.

6. Work the example

   For a=abc and b=ac, the table below reaches 2 at (3,2), giving ac. The runnable sample uses abcde and ace, whose LCS is uniquely ace of length 3. Skipping b and d in the first string demonstrates why contiguity is not required.

   a-prefix / b-prefix	empty	a	ac
   empty	0	0	0
   a	0	1	1
   ab	0	1	1
   abc	0	1	2

This is a complete program. Compile with C++17 and enter the input described below.

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
int main(){
    std::string a,b;
    std::getline(std::cin,a);
    std::getline(std::cin,b);
    int n=a.size(),m=b.size();
    std::vector<std::vector<int>>dp(n+1,std::vector<int>(m+1));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            dp[i][j]=a[i-1]==b[j-1]?dp[i-1][j-1]+1:std::max(dp[i-1][j],dp[i][j-1]);
        }
    }
    std::string answer;
    int i=n,j=m;
    while(i&&j){
        if(a[i-1]==b[j-1]){
            answer+=a[i-1];
            --i;
            --j;
        }
        else if(dp[i-1][j]>=dp[i][j-1]){
            --i;
        }
        else{
            --j;
        }
    } // Backtrack prefix states, then reverse.
    std::reverse(answer.begin(),answer.end());
    std::cout<<dp[n][m]<<'\n'<<answer<<'\n';
}

Complexity analysis

(n+1)(m+1) states with constant transitions give O(nm) time and O(nm) table space, plus O(n+m) backtracking. Length-only DP can use O(min(n, m)) memory as shown in the Space Optimization lesson.

Example input and output

Read two lines of lowercase letters, each length 0..2000. Print LCS length and one LCS; a length-zero answer has an empty second line.

Input

abcde
ace

Output

3
ace

For a=abc and b=ac, the table below reaches 2 at (3,2), giving ac. The runnable sample uses abcde and ace, whose LCS is uniquely ace of length 3. Skipping b and d in the first string demonstrates why contiguity is not required.

Practical applications

Use to compare ordered sequences, derive insertion/deletion-only distances and recover shared order. General edit distance also permits replacements and optimizes a different objective. The Strings folder remains a related introduction; this lesson emphasizes state derivation.

Check your understanding

What happens on a mismatch in LCS?

Put it into practice

Check the reconstructed result is a subsequence of both strings.