Longest Common Subsequence LCS

C++ code of Longest Common Subsequence Problem using Dynamic Programming.
snigdhaop · Oct 1, 2021 · 98a038d · 98a038d
1 parent 1660459
commit 98a038d
Showing 1 changed file with 35 additions and 0 deletions.
diff --git a/C++/Algorithms/Dyanmic Programming/Longest Common Subsequence.cpp b/C++/Algorithms/Dyanmic Programming/Longest Common Subsequence.cpp
@@ -0,0 +1,35 @@
+
+
+/*Given two sequences, find the length of longest subsequence present in both of them. Both the strings are of uppercase.*/
+
+#include<bits/stdc++.h>
+using namespace std;
+
+
+  //Function to find the length of longest common subsequence in two strings.
+    int lcs(int n, int m, string s1, string s2)
+    {
+        vector<vector<int>>dp(n+1,vector<int>(m+1,0));
+
+        for(int i=1;i<n+1;i++){
+            for(int j=1;j<m+1;j++){
+                if(s1[i-1]==s2[j-1])
+                dp[i][j]=1+dp[i-1][j-1];
+                else
+                dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
+            }
+        }
+        return dp[n][m];
+    }
+
+int main(){
+
+ int n,m;
+ cin>>n>>m;
+ string s1,s2;
+ cin>>s1>>s2;
+ int ans=0;
+ ans=lcs(n,m,s1,s2);
+ cout<<"Longest Common Subsequence "<<ans<<"\n";
+
+}