ronith
11/3/2018 - 4:06 AM

Longest Common Subsequence

Given two sequences, find the length of longest subsequence present in both of them. A subsequence is a sequence that appears in the same relative order, but not necessarily contiguous. For example, “abc”, “abg”, “bdf”, “aeg”, ‘”acefg”, .. etc are subsequences of “abcdefg”. So a string of length n has 2^n different possible subsequences. Examples: LCS for input Sequences “ABCDGH” and “AEDFHR” is “ADH” of length 3. LCS for input Sequences “AGGTAB” and “GXTXAYB” is “GTAB” of length 4.

Longest Common Subsequence.cpp
content_copyfile_download
//https://www.geeksforgeeks.org/longest-common-subsequence-dp-4/
#include <bits/stdc++.h>
using namespace std;

int main() {
    string s,t;
    getline(cin, s);
    getline(cin, t);
    int n= s.length(), m=t.length();

    int dp[n+1][m+1];
    for (int i=0;i<=n;i++) {
        for (int j=0;j<=m;j++) {
            if (i==0 || j==0)
                dp[i][j]= 0;
            else if (s[i-1]==t[j-1])
                dp[i][j]= 1+dp[i-1][j-1];
            else
                dp[i][j]= max(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout<< dp[n][m];
}