SHARE
TWEET

Untitled

a guest Jul 22nd, 2019 67 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define MAX 1000
  4. char str1[MAX],str2[MAX];
  5. int lenA,lenB;
  6. int dp[MAX][MAX];
  7. bool visited[MAX][MAX];
  8. int LCS(int i,int j)
  9. {
  10.     if(str1[i]=='\0' || str2[j]=='\0') return 0;
  11.     if(visited[i][j])return dp[i][j];
  12.  
  13.     int ans=0;
  14.     if(str1[i]==str2[j]) ans=1+LCS(i+1,j+1);
  15.     else
  16.     {
  17.         int val1=LCS(i+1,j);
  18.         int val2=LCS(i,j+1);
  19.         ans=max(val1,val2);
  20.     }
  21.     visited[i][j]=1;
  22.     dp[i][j]=ans;
  23.     return dp[i][j];
  24. }
  25. string ans;
  26. void printLCS(int i,int j)
  27. {
  28.     if(str1[i]=='\0' or str2[j]=='\0'){
  29.         cout<<ans<<endl;
  30.         return;
  31.     }
  32.     if(str1[i]==str2[j]){
  33.         ans+=str1[i];
  34.         printLCS(i+1,j+1);
  35.     }
  36.     else
  37.     {
  38.         if(dp[i+1][j]>dp[i][j+1]) printLCS(i+1,j);
  39.         else printLCS(i,j+1);
  40.     }
  41. }
  42. int main() {
  43.     scanf("%s%s",str1,str2);
  44.     lenA=strlen(str1);
  45.     lenB=strlen(str2);
  46.     LCS(0,0);
  47.     printLCS(0,0);
  48.     return 0;
  49.  
  50. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top