# Cod sursa(job #2303045)

Utilizator Data 15 decembrie 2018 14:27:59 Seif 0 cpp-64 done Arhiva de probleme 1.95 kb
``````#include <iostream>
#include <fstream>
using namespace std;
ifstream in("seif.in");
ofstream out("seif.out");
const int maxn = 1005;
int next1[maxn][maxn];
int next2[maxn][maxn];
int dp[maxn][maxn];
string A, B;

void solve()
{
for(int i = 0; i < maxn; i++)
{
for(int j = 0; j < maxn; j++)
dp[i][j] = 0;
for(int lit = 1; lit <= 26; lit++)
{
next1[i][lit] = 0;
next2[i][lit] = 0;
}
}
int k;
in >> k;
in >> A >> B;
int n = A.size();
int m = B.size();
A = " " + A;
B = " " + B;
for(int i = n; i >= 1; i--)
{
for(int j = m; j >= 1; j--)
{
if(A[i] != B[j])
dp[i][j] = max(dp[i + 1][j], dp[i][j + 1]);
else
dp[i][j] = dp[i + 1][j + 1] + 1;
}
}
for(int lit = 1; lit <= 26; lit++)
{
for(int i = n; i >= 1; i--)
{
if(A[i] - 'A' + 1 == lit)
next1[i][lit] = i;
else
next1[i][lit] = next1[i + 1][lit];
}
for(int i = m; i >= 1; i--)
{
if(B[i] - 'A' + 1 == lit)
next2[i][lit] = i;
else
next2[i][lit] = next2[i + 1][lit];
}
}
int poz1 = 1;
int poz2 = 1;
bool gasit = 1;
while(gasit)
{
gasit = 0;
for(int lit = 26; lit >= 1; lit--)
{
if(next1[poz1][lit] != 0 && next2[poz2][lit] != 0 && dp[next1[poz1][lit]][next2[poz2][lit]] >= k)
{
k = max(k - 1, 0);
poz1 = next1[poz1][lit] + 1;
poz2 = next2[poz2][lit] + 1;
gasit = 1;
out << (char)(lit + 'A' - 1);
}
}
}
out << "\n";
}

int main()
{
int T;
in >> T;
for(int i = 1; i <= T; i++)
solve();
return 0;
}
``````