#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template <class type1>
#define ll long long int
#define endl "\n"
#define ordered_set tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update>
using ordered_multiset = tree <type1, null_type, less_equal <type1>, rb_tree_tag, tree_order_statistics_node_update>;
//ordered_multiset <ll> kek;(declaration for multiorder set)
// ordered_set o_set;(declaration)
//kek.order_of_key(i);(strictly less then i for multi order set)
//o_set.order_of_key(5) ;(strictly less then i for multi order set)
#define yes cout << "YES\n"
#define no cout << "NO\n"
// int func(string &s,string &t, int n,int m,vector<vector<int>>&dp)
// {
// if(n<0||m<0)return 0;
// if(s[n]==t[m])
// {
// return 1+func(s,t,n-1,m-1,dp);
// }
// if(dp[n][m]!=-1)return dp[n][m];
// return dp[n][m]=max(func(s,t,n-1,m,dp),func(s,t,n,m-1,dp));
// }
// int lcs(string s, string t)
// {
// int i,j;
// vector<vector<int>>dp(s.size(),vector<int>(t.size(),-1));
// func(s,t,(int)s.size()-1,(int)t.size()-1,dp);
// for(i=0;i<s.size();i++)
// {
// for(j=0;j<t.size();j++)
// {
// cout<<dp[i][j]<<" ";
// }
// cout<<endl;
// }
// }
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string s,t;
cin>>s>>t;
ll n,m,i,j;
n=s.size();
m=t.size();
s="#"+s;
t="#"+t;
ll dp[n+1][m+1];
memset(dp,0,sizeof(dp));
for(i=0;i<=m;i++)dp[0][i]=0;
for(j=0;j<=n;j++)dp[j][0]=0;
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
{
if(s[i]==t[j])
{
dp[i][j]=1+dp[i-1][j-1];
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
}
}
}
// for(i=0;i<=n;i++)
// {
// for(j=0;j<=m;j++)cout<<dp[i][j]<< " ";
// cout<<endl;
// }
cout<<dp[n][m]<<endl;
ll r=dp[n][m];
char ans[r];
r--;
i=n;
j=m;
while(i>0&&j>0&&r>=0)
{
if(s[i]==t[j])
{
ans[r]=s[i];
i--;
j--;
r--;
}
else if(dp[i-1][j]>dp[i][j-1])
{
i--;
}
else j--;
}
cout<<ans<<endl;
return 0;
}
0 Comments