Cod sursa(job #138669)
#include <stdio.h>
#include <string.h>
#include <iostream.h>
int n, m, c[1002][1002], t, k;
int A[1001][33], B[1001][33];
char a[1001], b[101];
int max(int x, int y) {return x > y ? x : y;}
void init()
{
int i, j;
scanf("%d\n",&k);
scanf("%s",&a); scanf("%s",&b);
n = strlen(a); m = strlen(b);
memset(A,-1,sizeof(A)); memset(B,-1,sizeof(B)); memset(c,0,sizeof(c));
for (i = n - 1; i >= 0; i--)
for (j = 0; j < 26; j++)
if (a[i] == j+'A') A[i][j] = i;
else A[i][j] = A[i+1][j];
for (i = m - 1; i >= 0; i--)
for (j = 0; j < 26; j++)
if (b[i] == j+'A') B[i][j] = i;
else B[i][j] = B[i+1][j];
}
int main()
{
freopen("seif.in","r",stdin);
freopen("seif.out","w",stdout);
int i, j, urm, ok;
scanf("%d",&t);
while (t--)
{
init();
for(i = n - 1; i >= 0; i--)
for (j = m - 1; j >= 0; j--)
if (a[i] == b[j]) c[i][j] = c[i+1][j+1] + 1;
else c[i][j] = max (c[i+1][j],c[i][j+1]);
ok = 1; i = j = 0;
while (ok)
{
ok = 0;
for (urm = 25; urm >= 0; urm--)
if (A[i][urm] != -1 && B[j][urm] != -1)
if (c[A[i][urm]][B[j][urm]] >= k)
{
printf("%c", urm + 'A');
i = A[i][urm] + 1;
j = B[j][urm] + 1;
ok = 1;
break;
}
if (!ok) break;
k--;
}
printf("\n");
}
return 0;
}