# Cod sursa(job #2276094)

Utilizator Data 4 noiembrie 2018 10:14:05 Seif 100 cpp-64 done Arhiva de probleme 1.57 kb
``````#include <bits/stdc++.h>

using namespace std;

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

const int Nmax=1005;

int n,m,T,k;
int urm[2][Nmax][30];
int dp[Nmax][Nmax];
char a[Nmax],b[Nmax];

void Initializare()
{
for(int i=1;i<=n+1;i++)
for(int j=1;j<=m+1;j++)
dp[i][j]=0;

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]);

for(int i=1;i<=26;i++)
urm[0][n+1][i]=urm[1][m+1][i]=Nmax;

for(int i=n;i>=1;i--)
{
for(int j=1;j<=26;j++)
urm[0][i][j]=urm[0][i+1][j];

urm[0][i][a[i]-'A'+1]=i;
}

for(int i=m;i>=1;i--)
{
for(int j=1;j<=26;j++)
urm[1][i][j]=urm[1][i+1][j];

urm[1][i][b[i]-'A'+1]=i;
}
}

void Solutie()
{
int ok,pa,pb,na,nb;

pa=pb=ok=1;
while(ok)
{
ok=0;

for(int j=26;!ok && j>=1;j--)
{
na=urm[0][pa][j];
nb=urm[1][pb][j];

if(na<=n && nb<=m && dp[na][nb]>=k)
{
fout<<(char)(j+'A'-1);
pa=na+1;
pb=nb+1;
ok=1;
k--;
}
}
}

fout<<"\n";
}

int main()
{
fin>>T;

while(T--)
{
fin>>k;
fin>>(a+1)>>(b+1);
n=strlen(a+1);
m=strlen(b+1);

Initializare();
Solutie();
}

fin.close();
fout.close();
return 0;
}
``````