The Longest Common Subsequence (LCS) problem finds the longest sequence of characters that appears in both strings in the same relative order (not necessarily contiguous). The DP solution builds an (m+1)×(n+1) table and runs in O(mn) time, used in diff tools, version control, and bioinformatics.
int lcs(string& a, string& b) {
int m=a.size(), n=b.size();
vector<vector<int>> dp(m+1,vector<int>(n+1,0));
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
dp[i][j] = a[i-1]==b[j-1] ? dp[i-1][j-1]+1 : max(dp[i-1][j],dp[i][j-1]);
return dp[m][n];
}If a[i]==b[j]: dp[i][j]=dp[i-1][j-1]+1 (extend LCS by one). Otherwise: dp[i][j]=max(dp[i-1][j], dp[i][j-1]) (best LCS ignoring current char of a or b).
To reconstruct the actual LCS string: backtrack from dp[m][n]. If a[i-1]==b[j-1], include the character and go diagonal. Otherwise go in the direction of the larger neighbor.
LCS is the basis of Unix diff, git diff, DNA sequence alignment, and plagiarism detection. The edit distance between two strings is closely related to LCS length.
LCS stands for:
The time complexity of the DP LCS algorithm for strings of length m and n is:
If a[i] == b[j] in the LCS recurrence, dp[i][j] equals: