# Cod sursa(job #2490649)

Utilizator Data 10 noiembrie 2019 17:08:56 Seif 100 cpp-64 done Arhiva de probleme 1.77 kb
``````#include <bits/stdc++.h>
#define nmax 1005
#define inf 1e4

using namespace std;

ifstream fin("seif.in");
ofstream fout("seif.out");

int q;
int n, m, K;
char s1[nmax], s2[nmax];

int dp[nmax][nmax];
int next1[nmax][30], next2[nmax][30];

void prec()
{
int i,j;
for(i = 1; i <= n+1; i++)
for(j = 1; j <= m+1; j++)
dp[i][j] = 0;
for(i = n; i >= 1; i--)
for(j = m; j >= 1; j--)
if(s1[i] == s2[j])
dp[i][j] = 1 + dp[i+1][j+1];
else
dp[i][j] = max(dp[i+1][j],dp[i][j+1]);
for(i = 0; i < 26; i++)
next1[n+1][i] = next2[m+1][i] = nmax - 3;
for(i = n; i >= 1; i--)
{
for(j = 0; j < 26; j++)
next1[i][j] = next1[i+1][j];
next1[i][s1[i]-'A'] = i;
}
for(i = m; i >= 1; i--)
{
for(j = 0; j < 26; j++)
next2[i][j] = next2[i+1][j];
next2[i][s2[i]-'A'] = i;
}
}

void solve()
{
int p1 = 1, p2 = 1;
while (p1 <= n && p2 <= m)
{
int ch;
bool gasit = 0;
for (ch = 25; ch >= 0 && !gasit; ch--)
{
int n1 = next1[p1][ch];
int n2 = next2[p2][ch];
if (dp[n1][n2] >= K && n1 <= n && n2 <= m)
{
gasit = 1;
K--;
fout << s1[n1];
p1 = n1 + 1;
p2 = n2 + 1;
}
}
if (ch == -1 && !gasit)
break; //stop
}
fout << "\n";
}

int main()
{
fin >> q;
while (q--)
{
fin >> K;
fin >> (s1 + 1);
fin >> (s2 + 1);
n = strlen(s1 + 1);
m = strlen(s2 + 1);
prec();
solve();
}
return 0;
}
``````