stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (int)1e9 + 7

 

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

#define all(x) x.begin(),x.end()

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

#define sqr(x) ((x) * 1ll * (x))

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)3e3 + 7, MOD = (int)1e9 + 7;



string s,t;



string dp[4][N];



int main(){

		

	NFS



	cin >> s >> t;



	for(int i=1;i<=sz(s);i++){

		for(int j=1;j<=sz(t);j++){

			if(sz(dp[2][j-1])>sz(dp[2][j]))dp[2][j]=dp[2][j-1];

			if(sz(dp[2-1][j])>sz(dp[2][j]))dp[2][j]=dp[2-1][j];

			if(sz(dp[2-1][j-1])>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1];

			if(s[i-1]==t[j-1]){

				if(sz(dp[2-1][j-1])+1>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1]+s[i-1];

			}

		}

		for(int j=1;j<=sz(t);j++)dp[1][j]=dp[2][j],dp[2][j].clear();

	}

	

	cout << dp[1][sz(t)] << endl;

	

	ioi

}

// Faster C++ solution for the same problem (measured speedup: 1.3893129747428978x):
#include <iostream>

#include<utility>

#include<iomanip>

#include<cmath>

#include<algorithm>

#include<cfloat>

#include<functional>

#include<string>

#include<numeric>

#include<vector>

#include<stack>

#include<queue>

#include<set>

#include<map>

#include<cctype>

#include<iterator>

#include <stdio.h>

#include <string.h>

#include <sstream>

// #include <bits/stdc++.h>

//#include<conio.h>

#define ReadFile freopen("input.txt","r",stdin)

#define WriteFile freopen("output.txt","w",stdout)

#define MEGA_MIND ios_base::sync_with_stdio(0);cin.tie(0); cout.tie(0);

#define M_PI 3.14159265358979323846

#define mod 1000000007

#define endl "\n"

using namespace std;

using ll = long long;

using lli = long long int;

using ld = long double;





const int N = 5e5 + 5, inf = 9e9;







int main()

{

	MEGA_MIND



		string s, t, ans;

	cin >> s >> t;

	int m = s.size(), n = t.size();

	vector<vector<int>>dp(m + 1, vector<int>(n + 1));

	for (int i = 0; i <= m; i++)

	{

		for (int j = 0; j <= n; j++)

		{

			if (i == 0 || j == 0)

				dp[i][j] = 0;

			else if (s[i - 1] == t[j - 1])

				dp[i][j] = dp[i - 1][j - 1] + 1;

			else

				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);

		}

	} 

	int index = dp[m][n];

 

	int i = m, j = n;

	while (i > 0 && j > 0)

	{

		if (s[i - 1] == t[j - 1])

		{

			ans.push_back(s[i - 1]);

			i--;

			j--; 

			index--; 

		}



		else if (dp[i - 1][j] > dp[i][j - 1])

			i--;

		else

			j--;

	}



	reverse(ans.begin(), ans.end());

	cout << ans << endl;

	return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (int)1e9 + 7

 

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

#define all(x) x.begin(),x.end()

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

#define sqr(x) ((x) * 1ll * (x))

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)3e3 + 7, MOD = (int)1e9 + 7;



string s,t;



string dp[4][N];



int main(){

		

	NFS



	cin >> s >> t;



	for(int i=1;i<=sz(s);i++){

		for(int j=1;j<=sz(t);j++){

			if(sz(dp[2][j-1])>sz(dp[2][j]))dp[2][j]=dp[2][j-1];

			if(sz(dp[2-1][j])>sz(dp[2][j]))dp[2][j]=dp[2-1][j];

			if(sz(dp[2-1][j-1])>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1];

			if(s[i-1]==t[j-1]){

				if(sz(dp[2-1][j-1])+1>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1]+s[i-1];

			}

		}

		for(int j=1;j<=sz(t);j++)dp[1][j]=dp[2][j],dp[2][j].clear();

	}

	

	cout << dp[1][sz(t)] << endl;

	

	ioi

}

// Faster C++ solution for the same problem (measured speedup: 1.4138278739816652x):
#include <iostream>

#include <set>

#include <stack>

#include <vector>

#include <map>

#include <string>

#include <string.h>

#include <cstring>

#include <queue>

#include <algorithm>

#include <math.h>



using namespace std;



typedef long long ll;



int DP[3001][3001],BT[3001][3001];



int main()

{

	string s, t,name;

	cin >> s >> t;

	for (int i = 0; i < s.size() + 1; i++) 

	{

		for (int j = 0; j < t.size() + 1; j++) 

		{

			if (i == 0 || j == 0)

			{

				DP[i][j] = 0;

			}

			else if (s[i-1] == t[j-1]) 

			{

				DP[i][j] = DP[i - 1][j - 1] + 1;

				BT[i][j] = 0;

			}

			else 

			{

				DP[i][j] = max(DP[i][j - 1], DP[i - 1][j]);

				if (DP[i][j] == DP[i][j - 1])

				{

					BT[i][j] = 1;

				}

				else

					BT[i][j] = 2;

			}

		}

	}

	int i = s.size(), j = t.size();

	int temp = DP[i][j];

	name.resize(temp);

	while (true) 

	{

		if (i == 0 || j == 0)

			break;

		if (BT[i][j] == 0)

		{

			name[temp-1] = s[i-1];

			temp--;

			i--;

			j--;

		}

		if (BT[i][j] == 1) 

		{

			j--;

		}

		else if (BT[i][j] == 2)

		{

			i--;

		}

	}

	cout << name;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (int)1e9 + 7

 

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

#define all(x) x.begin(),x.end()

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

#define sqr(x) ((x) * 1ll * (x))

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)3e3 + 7, MOD = (int)1e9 + 7;



string s,t;



string dp[4][N];



int main(){

		

	NFS



	cin >> s >> t;



	for(int i=1;i<=sz(s);i++){

		for(int j=1;j<=sz(t);j++){

			if(sz(dp[2][j-1])>sz(dp[2][j]))dp[2][j]=dp[2][j-1];

			if(sz(dp[2-1][j])>sz(dp[2][j]))dp[2][j]=dp[2-1][j];

			if(sz(dp[2-1][j-1])>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1];

			if(s[i-1]==t[j-1]){

				if(sz(dp[2-1][j-1])+1>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1]+s[i-1];

			}

		}

		for(int j=1;j<=sz(t);j++)dp[1][j]=dp[2][j],dp[2][j].clear();

	}

	

	cout << dp[1][sz(t)] << endl;

	

	ioi

}

// Faster C++ solution for the same problem (measured speedup: 1.391001433552778x):
#include <bits/stdc++.h>

using namespace std;

string lcs(string text1, string text2) {

        vector<vector<int>> dp(text1.size()+1,vector<int>(text2.size()+1,0));

        for(int i=1;i<dp.size();i++){

            for(int j=1;j<dp[1].size();j++){

                if(text1[i-1]==text2[j-1]){

                    dp[i][j]= 1+ dp[i-1][j-1];//just before consderng t1[i] & t2[j] lcs length was dp[i-1][j-1;]

                }

                else

                    dp[i][j]= max(dp[i-1][j],dp[i][j-1]);

            }

        }

        //printing lcs;

        int i=dp.size()-1, j=dp[0].size()-1;

        string ans="";

        while(1){

            if(i<1||j<1) break;

            if(dp[i][j-1]==dp[i][j]){

                --j;

                continue;

            } 

            else if(dp[i-1][j]==dp[i][j] ){ 

                --i;

                continue;

            }

            else if( text1[i-1]==text2[j-1] && dp[i][j]==dp[i-1][j-1]+1){

                ans=text1[i-1]+ans;

                --i;--j;

            }           

            // if(dp[i][j]==0)

            //     break;

        }

        // reverse(ans.begin(),ans.end());

        return ans;

    }

    

    int main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    cout.tie(NULL);

    string s,t;

    cin>>s>>t;

    cout<<lcs(s,t);

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (int)1e9 + 7

 

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

#define all(x) x.begin(),x.end()

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

#define sqr(x) ((x) * 1ll * (x))

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)3e3 + 7, MOD = (int)1e9 + 7;



string s,t;



string dp[4][N];



int main(){

		

	NFS



	cin >> s >> t;



	for(int i=1;i<=sz(s);i++){

		for(int j=1;j<=sz(t);j++){

			if(sz(dp[2][j-1])>sz(dp[2][j]))dp[2][j]=dp[2][j-1];

			if(sz(dp[2-1][j])>sz(dp[2][j]))dp[2][j]=dp[2-1][j];

			if(sz(dp[2-1][j-1])>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1];

			if(s[i-1]==t[j-1]){

				if(sz(dp[2-1][j-1])+1>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1]+s[i-1];

			}

		}

		for(int j=1;j<=sz(t);j++)dp[1][j]=dp[2][j],dp[2][j].clear();

	}

	

	cout << dp[1][sz(t)] << endl;

	

	ioi

}

// Faster C++ solution for the same problem (measured speedup: 1.404184712207949x):
#include <bits/stdc++.h>

#define fi first

#define se second

#define pb push_back



using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<long long, long long> pll;



int dp[3009][3009];

string s, t, ans = "";



int main()

{

    ios_base::sync_with_stdio(0);

    cin.tie(NULL);



    cin >> s >> t;



    for (int i = 1; i <= s.size(); i++)

    {

        for (int j = 1; j <= t.size(); j++)

        {

            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);



            if (s[i - 1] == t[j - 1])

            {

                dp[i][j] = max(dp[i][j], dp[i - 1][j - 1] + 1);

            }

        }

    }



    int n = s.size(), m = t.size();

    while (n > 0 && m > 0)

    {

        if (s[n - 1] == t[m - 1])

        {

            ans += t[m - 1];

            n--;

            m--;

        }

        else

        {

            if (dp[n - 1][m] > dp[n][m - 1])

            {

                n--;

            }

            else

            {

                m--;

            }

        }

    }



    reverse(ans.begin(), ans.end());



    cout << ans << "\n";

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (int)1e9 + 7

 

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

#define all(x) x.begin(),x.end()

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

#define sqr(x) ((x) * 1ll * (x))

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)3e3 + 7, MOD = (int)1e9 + 7;



string s,t;



string dp[4][N];



int main(){

		

	NFS



	cin >> s >> t;



	for(int i=1;i<=sz(s);i++){

		for(int j=1;j<=sz(t);j++){

			if(sz(dp[2][j-1])>sz(dp[2][j]))dp[2][j]=dp[2][j-1];

			if(sz(dp[2-1][j])>sz(dp[2][j]))dp[2][j]=dp[2-1][j];

			if(sz(dp[2-1][j-1])>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1];

			if(s[i-1]==t[j-1]){

				if(sz(dp[2-1][j-1])+1>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1]+s[i-1];

			}

		}

		for(int j=1;j<=sz(t);j++)dp[1][j]=dp[2][j],dp[2][j].clear();

	}

	

	cout << dp[1][sz(t)] << endl;

	

	ioi

}

// Faster C++ solution for the same problem (measured speedup: 1.394206150997005x):
#include <bits/stdc++.h>

using namespace std;



#define ll long long

#define ull unsigned ll



#define vi vector <int>

#define ii pair <int, int>

#define vii vector <ii>

#define INFLL 9e18

#define INF 2e9

#define EPS 1e-9

#define pb push_back

#define emp emplace_back

#define PI acos(-1.0)

#define endl "\n"

#define mp make_pair

#define DEBUG 0





int main ()



{

    //#define int ll

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);

    //cout.tie(NULL);



    //freopen("input.txt", "r", stdin); 

    //freopen("output.txt", "w", stdout);

    string s, t;

    cin >> s >> t;

    int m = s.size();

    int n = t.size();

    int dp[m+1][n+1];



    for (int i=0; i<=m; i++){

        dp[i][0] = 0;

    }

    for (int i=0; i<=n; i++){

        dp[0][i] = 0;

    }

    string lcs = "";

    for (int i=1; i<=m; i++){

        for (int j = 1; j<=n; j++){

            if (s[i-1] == t[j-1]){

                dp[i][j] = 1 + dp[i-1][j-1];

                

            }

            else dp[i][j] = max(dp[i-1][j], dp[i][j-1]);

        }

    }



    int i = m;

    int j = n;

    while (i > 0 and j > 0){

        if (s[i-1] == t[j-1]) {

            lcs += s[i-1];

            i--;

            j--;

        }

        else if (dp[i-1][j] > dp[i][j-1]) i--;

        else j--;

    }

    reverse(lcs.begin(), lcs.end());



    //cout << dp[m][n] << endl;

    cout << lcs << endl;

       

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (int)1e9 + 7

 

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

#define all(x) x.begin(),x.end()

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

#define sqr(x) ((x) * 1ll * (x))

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)3e3 + 7, MOD = (int)1e9 + 7;



string s,t;



string dp[4][N];



int main(){

		

	NFS



	cin >> s >> t;



	for(int i=1;i<=sz(s);i++){

		for(int j=1;j<=sz(t);j++){

			if(sz(dp[2][j-1])>sz(dp[2][j]))dp[2][j]=dp[2][j-1];

			if(sz(dp[2-1][j])>sz(dp[2][j]))dp[2][j]=dp[2-1][j];

			if(sz(dp[2-1][j-1])>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1];

			if(s[i-1]==t[j-1]){

				if(sz(dp[2-1][j-1])+1>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1]+s[i-1];

			}

		}

		for(int j=1;j<=sz(t);j++)dp[1][j]=dp[2][j],dp[2][j].clear();

	}

	

	cout << dp[1][sz(t)] << endl;

	

	ioi

}

// Faster C++ solution for the same problem (measured speedup: 1.4384267490441125x):
#include<bits/stdc++.h> 

using namespace std; 

#define MAXC 3000



char cads[MAXC+1], cadt[MAXC+1];

int dp[MAXC+1][MAXC+1];



int s,t;

char lcs[MAXC+1];



int main() { 

	int i,j;

        int posicion;

	scanf("%s",cads);

	scanf("%s",cadt);

	s=strlen(cads); t = strlen(cadt);

	for (i=0; i<=s; i++) {

		dp[i][0]=0;

	}

	for (j=1; j<=t; j++) {

		dp[0][j]=0;

	}



	for (i=1;i<=s; i++) {

		for (j=1; j<=t; j++) {

			if (cads[i-1]==cadt[j-1]) {

				dp[i][j]=dp[i-1][j-1]+1;

			}

			else {

				dp[i][j]=max(dp[i-1][j],dp[i][j-1]);

			}

		}

	}

	/*for (i=0; i<=s; i++) {

		for (j=0; j<=t; j++) {

			printf("%5d", dp[i][j]);

		}

		printf("\n");

	}

	printf("%d\n",dp[s][t]);*/

	posicion=dp[s][t];

	lcs[posicion]=0;

	for (i=s, j=t; i>0 && j>0; ) {

		if (cads[i-1]==cadt[j-1]) {

			posicion--; i--; j--;

			lcs[posicion]=cads[i];

		}

		else if (dp[i-1][j]>dp[i][j-1]) {

			i--;

		}

		else { 

			j--; 

		}

	}

	printf("%s\n", lcs);

	return 0; 

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (int)1e9 + 7

 

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

#define all(x) x.begin(),x.end()

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

#define sqr(x) ((x) * 1ll * (x))

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)3e3 + 7, MOD = (int)1e9 + 7;



string s,t;



string dp[4][N];



int main(){

		

	NFS



	cin >> s >> t;



	for(int i=1;i<=sz(s);i++){

		for(int j=1;j<=sz(t);j++){

			if(sz(dp[2][j-1])>sz(dp[2][j]))dp[2][j]=dp[2][j-1];

			if(sz(dp[2-1][j])>sz(dp[2][j]))dp[2][j]=dp[2-1][j];

			if(sz(dp[2-1][j-1])>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1];

			if(s[i-1]==t[j-1]){

				if(sz(dp[2-1][j-1])+1>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1]+s[i-1];

			}

		}

		for(int j=1;j<=sz(t);j++)dp[1][j]=dp[2][j],dp[2][j].clear();

	}

	

	cout << dp[1][sz(t)] << endl;

	

	ioi

}

// Faster C++ solution for the same problem (measured speedup: 1.403096098947368x):
#include <algorithm>

#include <bitset>

#include <cctype>

#include <cerrno>

#include <clocale>

#include <cmath>

#include <complex>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <ctime>

#include <deque>

#include <exception>

#include <fstream>

#include <functional>

#include <limits>

#include <list>

#include <map>

#include <iomanip>

#include <ios>

#include <iosfwd>

#include <iostream>

#include <istream>

#include <ostream>

#include <queue>

#include <set>

#include <sstream>

#include <stack>

#include <stdexcept>

#include <streambuf>

#include <string>

#include <utility>

#include <vector>

#include <cwchar>

#include <cwctype>

using namespace std;

#define IO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)

const int inf = 0x3f3f3f3f;

typedef long long ll;

const int maxn = 3500;

const ll mod = 1e9 + 7;

char s[maxn],t[maxn];

int dp[maxn][maxn];

int main() {

    IO;

    cin>>s+1;

    cin>>t+1;

    int len=strlen(s+1),len1=strlen(t+1);

    for(int i=len;i>=1;i--) {

        for(int j=len1;j>=1;j--) {

            if(s[i]==t[j]) {

                dp[i][j]=dp[i+1][j+1]+1;

            }

            else {

                dp[i][j]=max(dp[i][j+1],dp[i+1][j]);

            }

        }

    }

    int l=1,r=1;

    while(l<=len&&r<=len1) {

        if(s[l]==t[r]) {

            cout<<s[l];

            l++,r++;

        }

        else if(dp[l][r]==dp[l+1][r]) {

            l++;

        }

        else r++;

    }

    puts("");

    

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (int)1e9 + 7

 

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

#define all(x) x.begin(),x.end()

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

#define sqr(x) ((x) * 1ll * (x))

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)3e3 + 7, MOD = (int)1e9 + 7;



string s,t;



string dp[4][N];



int main(){

		

	NFS



	cin >> s >> t;



	for(int i=1;i<=sz(s);i++){

		for(int j=1;j<=sz(t);j++){

			if(sz(dp[2][j-1])>sz(dp[2][j]))dp[2][j]=dp[2][j-1];

			if(sz(dp[2-1][j])>sz(dp[2][j]))dp[2][j]=dp[2-1][j];

			if(sz(dp[2-1][j-1])>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1];

			if(s[i-1]==t[j-1]){

				if(sz(dp[2-1][j-1])+1>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1]+s[i-1];

			}

		}

		for(int j=1;j<=sz(t);j++)dp[1][j]=dp[2][j],dp[2][j].clear();

	}

	

	cout << dp[1][sz(t)] << endl;

	

	ioi

}

// Faster C++ solution for the same problem (measured speedup: 1.4277039611753934x):
#include <bits/stdc++.h>

using namespace std;



const int maxn = 3010;

char str1[maxn];

char str2[maxn];

int dp[maxn][maxn];

char path[maxn];



int main()

{

	cin.getline(str1,maxn);

	cin.getline(str2,maxn);

    int len1 = strlen(str1);

    int len2 = strlen(str2);

    

    //LCS 

    for(int i = 0; i < len1; ++i){

        for(int j = 0; j < len2; ++j){

            if(str1[i] == str2[j])

                dp[i+1][j+1] = dp[i][j]+1;

            else

                dp[i+1][j+1] = max(dp[i+1][j],dp[i][j+1]);

        }

    }

    

    int i = len1-1;

    int j = len2-1;

    int plen = 0;

    //记录路径

    while(i >= 0 && j >= 0){

        if(str1[i] == str2[j]){

            path[plen++] = str1[i];

            --i;

            --j;

        }

        else if(dp[i+1][j] >= dp[i][j+1])//说明lcs是str1[0~i]和str2[0~j-1]的lcs

            --j;

        else

            --i;

    }

    for(int i = plen-1; i >= 0; --i)

        cout<<path[i];

    cout<<endl;

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

#define ll long long

#define ld long double

#define ull unsigned ll

#define ioi exit(0);

 

#define f first

#define s second

 

#define inf (int)1e9 + 7

 

#define NFS ios_base :: sync_with_stdio(0), cin.tie(0), cout.tie(0);

 

#define mp(x,y) make_pair(x,y)

 

#define lb(x) lower_bound(x)

#define ub(x) upper_bound(x)

 

#define pb push_back

#define ppb pop_back

 

#define bitcoin __builtin_popcount

 

#define endl "\n"

 

#define in(x) insert(x)

 

#define sz(x) (int)x.size()

 

#define all(x) x.begin(),x.end()

 

#define pw2(x) (1ll<<x) //2^x

 

#define forit(it,v) for (typeof(v.begin()) it = v.begin(); it != v.end(); ++it)

 

#define sqr(x) ((x) * 1ll * (x))

 

#define UpdateRandom srand (time(NULL));

 

using namespace std;

 

const int N = (int)3e3 + 7, MOD = (int)1e9 + 7;



string s,t;



string dp[4][N];



int main(){

		

	NFS



	cin >> s >> t;



	for(int i=1;i<=sz(s);i++){

		for(int j=1;j<=sz(t);j++){

			if(sz(dp[2][j-1])>sz(dp[2][j]))dp[2][j]=dp[2][j-1];

			if(sz(dp[2-1][j])>sz(dp[2][j]))dp[2][j]=dp[2-1][j];

			if(sz(dp[2-1][j-1])>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1];

			if(s[i-1]==t[j-1]){

				if(sz(dp[2-1][j-1])+1>sz(dp[2][j]))dp[2][j]=dp[2-1][j-1]+s[i-1];

			}

		}

		for(int j=1;j<=sz(t);j++)dp[1][j]=dp[2][j],dp[2][j].clear();

	}

	

	cout << dp[1][sz(t)] << endl;

	

	ioi

}

// Faster C++ solution for the same problem (measured speedup: 1.4085923768452366x):
#include <bits/stdc++.h>

#define re register

#define LL long long

#define SIZE 3005

#define INF 0x7f7f7f7f

#define S size()

using namespace std;

string s1,s2,ans;

int dp[SIZE][SIZE],p[SIZE][SIZE];

inline void dfs(int i,int j)

{

	if(i==0 || j==0)

		return;

	if(p[i][j]==1)

		dfs(i-1,j-1),cout<<s1[i];

	else	if(p[i][j]==2)

		dfs(i-1,j);

	else

		dfs(i,j-1);

}

int main()

{

	s1=s2=' ';

	string a,b;

	cin>>a>>b;

	s1+=a;s2+=b;

	for(re int i=1;i<s1.S;++i)

		for(re int j=1;j<s2.S;++j)

			if(s1[i]==s2[j])

				dp[i][j]=dp[i-1][j-1]+1,p[i][j]=1;

			else if(dp[i-1][j]>dp[i][j-1])

				dp[i][j]=dp[i-1][j],p[i][j]=2;

			else

				dp[i][j]=dp[i][j-1],p[i][j]=3;

	dfs(s1.S-1,s2.S-1);

	cout<<endl;

	return 0;

}