Cod sursa(job #153088)
#include<stdio.h>
#include<string.h>
#define lg 1005
int k, x1, x2, d[lg][lg], a1[100][lg], a2[100][lg], i, j, p1, p2, l1, l2;
char s1[lg], s2[lg];
inline int max(int a, int b){
if (a > b)
return a;
return b;
}
void golire(){
for (int i = 0; i < x1; i ++)
for (int j = 0; j < x2; j ++)
d[i][j] = 0;
for (int i = 'Z'; i >= 'A'; i --){
for (int j = 0; j < x1; j ++)
a1[i][j] = 0;
for (int j = 0; j < x2; j ++)
a2[i][j] = 0;
}
}
int main()
{
freopen("seif.in", "rt", stdin);
freopen("seif.out", "wt", stdout);
int teste;
scanf("%d", &teste);
while (teste --){
scanf("%d\n", &k);
scanf("%s%s", s1, s2);
x1 = strlen(s1), x2 = strlen(s2);
for (i = x1-1; i >= 0; i --)
for (j = x2-1; j >= 0; j --){
if (s1[i] == s2[j])
d[i][j] = d[i+1][j+1] + 1;
else
d[i][j] = max(d[i+1][j], d[i][j+1]);
//printf("cel mai mare kkt intre %d si %d este %d\n", i, j, d[i][j]);
}
for (j = 'Z'; j >= 'A'; j --){
for (i = x1-1; i >= 0; i --)
if (s1[i] == j)
a1[j][i] = i+1;
else
a1[j][i] = a1[j][i+1];
//printf("aparitia lui %c de la %d este la %d\n", j, i, a1[j][i]);
for (i = x2-1; i >= 0; i --)
if (s2[i] == j)
a2[j][i] = i+1;
else
a2[j][i] = a2[j][i+1];
}
p1 = 0, p2 = 0;
while (p1 < x1 && p2 < x2)
for (i = 'Z'; i >= 'A'; i --){
l1 = a1[i][p1];
l2 = a2[i][p2];
//printf("sunt la %c cu %d si %d si obtin %d %d -->", i, p1, p2, l1, l2);
if (l1 && l2){
l1 --, l2 --;
if (d[l1+1][l2+1] >= k-1){
k --;
//printf("am intrat---->\n");
printf("%c", i);
p1 = l1+1, p2 = l2+1;
break;
}
}
//printf("\n");
}
printf("\n");
golire();
}
return 0;
}