Advertisement
Saleh127

LCS with path printing

Oct 15th, 2021
1,101
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.00 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
  5. ll dp[3005][3005];
  6.  
  7. int main()
  8. {
  9.    ios_base::sync_with_stdio(0);
  10.    cin.tie(0);cout.tie(0);
  11.  
  12.    string a;
  13.    string b;
  14.  
  15.    ll n,m,i,j,k,l;
  16.  
  17.    cin>>a>>b;
  18.  
  19.    n=a.size();
  20.    m=b.size();
  21.  
  22.    //dp[0][0]=0;
  23.  
  24.    for(i=0;i<n;i++) dp[i][0]=0;
  25.    for(i=0;i<m;i++) dp[0][i]=0;
  26.  
  27.  
  28.    for(i=1;i<=n;i++)
  29.    {
  30.         for(j=1;j<=m;j++)
  31.         {
  32.              if(a[i-1]==b[j-1])
  33.              {
  34.                   dp[i][j]=dp[i-1][j-1]+1;
  35.              }
  36.              else
  37.              {
  38.                   dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
  39.              }
  40.         }
  41.    }
  42.  
  43.    i=n,j=m;
  44.  
  45.    string ans="";
  46.  
  47.    l=dp[n][m];
  48.  
  49.    while(l--)
  50.    {
  51.         while(i>0 && dp[i-1][j]==dp[i][j]) i--;
  52.         while(j>0 && dp[i][j-1]==dp[i][j]) j--;
  53.  
  54.         i--,j--;
  55.         ans+=a[i];
  56.    }
  57.  
  58.    reverse(ans.begin(),ans.end());
  59.  
  60.    cout<<ans<<endl;
  61.  
  62.  
  63.    return 0;
  64. }
  65.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement