# Cod sursa(job #2049502)

Utilizator Data 27 octombrie 2017 12:13:45 Seif 0 cpp done Arhiva de probleme 2.31 kb
``````#include <bits/stdc++.h>
using namespace std;

int n, m, t, k;
int d[1005][1005], nxt[1005][1005];
char a[1005], b[1005], sol[1005];
char s[1005];
inline void rec(int L, int L1, int L2, char s[]){
if(L1 > n || L2 > m) return ;
//    if(nxt[L1][L2]){
//        if(nxt[L1][L2] == 1) ++L1;
//        if(nxt[L1][L2] == 2) ++L2;
//        if(nxt[L1][L2] == 3) {
//            s[L++] = s[L1];
//            ++L2, ++L1;
//        }
//        rec(L, L1, L2, s);
//        return ;
//    }
char aux[5][1005];
memset(aux, 0, sizeof(aux));
int NR = -1;
if(d[L1 + 1][L2] == d[L1][L2]){
++NR;
strcpy(aux[NR], s);
rec(L, L1 + 1, L2, s);
}
if(d[L1][L2 + 1] == d[L1][L2]){
++NR;
strcpy(aux[NR], s);
rec(L, L1, L2 + 1, s);
}
if(d[L1 + 1][L2 + 1] == d[L1][L2] - 1){
++NR;
strcpy(aux[NR], s);
aux[NR][L] = a[L1];
rec(L + 1, L1 + 1, L2 + 1, s);
}
if(L >= k) strcpy(aux[++NR], s);
int w = 0;
strcpy(s, aux[0]);
for(int i = 1; i <= NR ; ++i)
if(strcmp(aux[i], s) > 0) strcpy(s, aux[i]), w = i;
}
int main()
{
freopen("seif.in", "r", stdin);
freopen("seif.out", "w", stdout);
scanf("%d", &t);
while(t--){
scanf("%d", &k);
scanf("%s", a + 1);
scanf("%s", b + 1);
int L1 = strlen(a + 1), L2 = strlen(b + 1);
memset(d, 0, sizeof(d));
for(int i = L1; i >= 1 ; --i){
for(int j = L2; j >= 1 ; --j){
if(a[i] == b[j]) d[i][j] = d[i + 1][j + 1] + 1;
else d[i][j] = max(d[i + 1][j], d[i][j + 1]);
}
}
char Max = 'A';
for(int i = 1; i <= L1 ; ++i)
for(int j = 1; j <= L2 ; ++j)
if(a[i] == b[j] && d[i][j] >= k)
if(a[i] > Max) Max = a[i];
memset(sol, 0, sizeof(sol));
n = L1; m = L2;
for(int i = 1; i <= L1 ; ++i){
for(int j = 1; j <= L2 ; ++j){
if(a[i] == b[j] && d[i][j] >= k && a[i] == Max){
s[0] = a[i];
rec(1, i + 1, j + 1, s);
if(strcmp(sol, s) < 1) strcpy(sol, s);
}
}
}
printf("%s\n", sol);

}
return 0;
}
``````