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\nGXTXAYB
Output:
4
Solution in C++
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
int main(){
string s1, s2;
getline(cin, s1);
getline(cin, s2);
int n = s1.size(), m = s2.size();
vector<vector<int>> dp(n+1, vector<int>(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;
}