# Cod sursa(job #2007361)

Utilizator Data 2 august 2017 16:21:29 Seif 100 cpp done Arhiva de probleme 1.16 kb
``````#include <bits/stdc++.h>
using namespace std;

ifstream fi("seif.in");
ofstream fo("seif.out");

const int N = 1024, S = 26;

int dp[N][N], na[N][S], nb[N][S];
char a[N], b[N];

int n, m, k;

void solve() {
int x, y;
bool flag;

fi >> k >> (a + 1) >> (b + 1);

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

memset(dp, 0x00, sizeof dp);
memset(na, 0x00, sizeof na);
memset(nb, 0x00, sizeof nb);

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

for (int i = n; i >= 1; --i) {
for (int ch = 0; ch < S; ++ch)
na[i][ch] = na[i + 1][ch];
na[i][a[i] - 'A'] = i; }

for (int i = m; i >= 1; --i) {
for (int ch = 0; ch < S; ++ch)
nb[i][ch] = nb[i + 1][ch];
nb[i][b[i] - 'A'] = i; }

x = y = 1;
do {
flag = false;
for (int ch = 25; ch >= 0; --ch)
if (na[x][ch] && nb[y][ch] && dp[na[x][ch] + 1][nb[y][ch] + 1] >= k - 1) {
fo << char(ch + 'A');
x = na[x][ch] + 1;
y = nb[y][ch] + 1;
flag = true;
--k;
break; } }
while (flag);

fo << '\n'; }

int main() {
int tsk;

fi >> tsk;
while (tsk--)
solve();

return 0; }

``````