Problem 11: Longest Common Subsequence

Problem Statement: Given two strings, compute the length of their longest common subsequence using dynamic programming.

Input

Two lines each containing a string.

Output

Print the length of the longest common subsequence.

Examples


Input:
AGGTAB
GXTXAYB

Output:
4

Solution Explanation

Method 1: Build a DP table where dp[i][j] represents the LCS length of the first i and first j characters; use recurrence comparing characters. Method 2: Use recursion with memoization to solve the problem top-down, although it is less efficient.

Solution in C++


#include 
#include 
#include 
#include 
using namespace std;

int main(){
    string s1, s2;
    getline(cin, s1);
    getline(cin, s2);
    int n = s1.size(), m = s2.size();
    vector> dp(n+1, vector(m+1, 0));
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(s1[i-1] == s2[j-1])
                dp[i][j] = dp[i-1][j-1] + 1;
            else
                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
        }
    }
    cout << dp[n][m];
    return 0;
}