Cod sursa(job #150694)
#include<stdio.h>
#include<string.h>
#define lg 1005
int k, n1, n2, nr, i, j, d[lg][lg], dr[95][lg], st[95][lg], p1, p2, h, l1, l2;
char s1[lg], s2[lg], sir[lg];
inline int max(int a, int b){
if (a > b)
return a;
return b;
}
void gol(){
for (int i = 0; i <= nr; i ++)
sir[i] = 0;
for (int i = 0; i < n1; i ++)
for (int j = 0; j < n2; j ++)
d[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", s1);
scanf("%s", s2);
n1 = strlen(s1), n2 = strlen(s2);
for (i = n1-1; i >= 0; i --)
for (j = n2-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]);
for (i = 'Z'; i >= 'A'; i --)
for (j = n1-1; j >= 0; j --)
if (s1[j] == i)
dr[i][j] = j+1;
else
dr[i][j] = dr[i][j+1];
for (i = 'Z'; i >= 'A'; i --)
for (j = n2-1; j >= 0; j --)
if (s2[j] == i)
st[i][j] = j+1;
else
st[i][j] = st[i][j+1];
l1 = 0, l2 = 0;
while (l1 < n1 && l2 < n2)
for (i = 'Z'; i >= 'A'; i --){
p1 = dr[i][l1];
p2 = st[i][l2];
if (p1 && p2){
p1 --, p2 --;
if (d[p1+1][p2+1] >= k-1){
k --;
printf("%c", i);
l1 = p1+1, l2 = p2+1;
break;
}
}
}
printf("\n");
gol();
}
return 0;
}