lcs.cpp

#include <bits/stdc++.h>
#define MOD 1000000007
#define pb push_back
#define bw(i,r,l) for (int i=r-1;i>=l;i--)
#define fw(i,l,r) for (int i=l;i<r;i++)
using namespace std;
typedef pair<int,int> ii;
string s,t; int dp[101][101];
ii r[101][101];
void get(int i,int j) {
	if (!i&&!j) return;
	ii temp=r[i][j];
	get(temp.first,temp.second);
	if (temp.first<i&&temp.second<j) cout<<s[temp.first];
}
signed main() {
	//freopen("aome.inp","r",stdin);
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	cin>>s>>t;
	memset(dp,-1,sizeof(dp));
	dp[0][0]=0;
	fw (i,0,s.length()+1) fw (j,0,t.length()+1) if (dp[i][j]!=-1) {
		if (i<s.length()) {
			if (dp[i][j]>dp[i+1][j]) {
				dp[i+1][j]=dp[i][j];
				r[i+1][j]=ii(i,j);
			}
		}
		if (j<t.length()) {
			if (dp[i][j]>dp[i][j+1]) {
				dp[i][j+1]=dp[i][j];
				r[i][j+1]=ii(i,j);
			}
		}
		if (i<s.length()&&j<t.length()) {
			if (s[i]==t[j]) {
				if (dp[i][j]+1>dp[i+1][j+1]) {
					dp[i+1][j+1]=dp[i][j]+1;
					r[i+1][j+1]=ii(i,j);
				}
			}
		}
	}
	cout<<dp[s.length()][t.length()]<<"\n";
	get(s.length(),t.length());
	return 0;
}