# include < iostream >
# include < string >
using namespace std ;
string maximizeOverlap ( const string &S1, const string &S2) {
int m = S1. length ();
int n = S2. length ();
int dp [m + 1 ][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 (S1[i - 1 ] == S2[j - 1 ]) {
dp [i][j] = dp [i - 1 ][j - 1 ] + 1 ;
} else {
dp [i][j] = max ( dp [i - 1 ][j], dp [i][j - 1 ]);
}
}
}
string result = "" ;
int i = m, j = n;
while (i > 0 && j > 0 ) {
if (S1[i - 1 ] == S2[j - 1 ]) {
result = S1[i - 1 ] + result ;
i--;
j--;
} else {
if ( dp [i - 1 ][j] > dp [i][j - 1 ]) {
result = " " + result ;
i--;
} else {
j--;
}
}
}
while (i > 0 ) {
result = " " + result ;
i--;
}
return result ;
}
int main () {
string S1, S2;
cout << " Introduceti primul sir: " ;
cin >> S1;
cout << " Introduceti al doilea sir: " ;
cin >> S2;
string result = maximizeOverlap (S1, S2);
cout << " Sirul S1 modificat este: " << result << endl ;
return 0 ;
}