Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #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;
- }
Add Comment
Please, Sign In to add comment