# Cod sursa(job #2310089)

Utilizator Data 30 decembrie 2018 16:18:21 Seif 100 cpp-64 done Arhiva de probleme 1.97 kb
``````#include <bits/stdc++.h>
#define all(cont) cont.begin(), cont.end()
#define pb push_back
#define fi first
#define se second
#define DEBUG(x) cerr << (#x) << ": " << (x) << '\n'

using namespace std;

typedef pair <int, int> pii;
typedef vector <int> vi;
typedef long long ll;
typedef unsigned long long ull;

const int NMAX = 1005;
const int SIGMA = 26;

int n, m, k;
char a[NMAX], b[NMAX];
int next_char[2][NMAX][SIGMA + 5];
int dp[NMAX][NMAX];

void getNextChar (int x) {
int l = (x == 0) ? n : m;
for (int i = l; i >= 1; --i) {
for (int j = 0; j < SIGMA; ++j) {
next_char[x][i][j] = next_char[x][i + 1][j];
}
next_char[x][i][((x == 0) ? (a[i] - 'A') : (b[i] - 'A'))] = i;
}
}

void solveTest() {
scanf ("%d\n%s%s", &k, (a + 1), (b + 1));

n = strlen (a + 1);
m = strlen (b + 1);

memset (dp, 0, sizeof (dp));
for (int i = n; i >= 1; --i) {
for (int j = m; j >= 1; --j) {
if (a[i] == b[j]) dp[i][j] = 1 + dp[i + 1][j + 1];
else dp[i][j] = max (dp[i + 1][j], dp[i][j + 1]);
}
}

memset (next_char, 0, sizeof (next_char));
getNextChar (0);
getNextChar (1);

int posa = 1, posb = 1;

bool ok = false;
while (!ok) {
ok = true;
for (int i = SIGMA - 1; i >= 0; --i) {
int next_posa = next_char[0][posa][i];
int next_posb = next_char[1][posb][i];
if (next_posa && next_posb) {
if (dp[next_posa][next_posb] >= k) {
printf ("%c", a[next_posa]);
posa = next_posa + 1;
posb = next_posb + 1;
--k;
ok = false;
break;
}
}
}
}
printf ("\n");
}

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef LOCAL_DEFINE
freopen (".in", "r", stdin);
#endif

freopen ("seif.in", "r", stdin);
freopen ("seif.out", "w", stdout);

int t;
scanf ("%d\n", &t);
while (t--) {
solveTest();
}

fclose (stdin);
fclose (stdout);
return 0;
}
``````