Cod sursa(job #186129)
#include <cstdio>
#include <cstring>
#include <iostream>
#define DIM 1024
using namespace std;
int T, K, N, M, C[DIM][DIM], nextA[DIM][35], nextB[DIM][35];
char A[DIM], B[DIM];
int main()
{
FILE *fin = fopen("seif.in", "r");
FILE *fout = fopen("seif.out", "w");
fscanf(fin, "%d", &T);
for (int i = 1; i <= T; i++)
{
char ch;
fscanf(fin, "%d", &K);
fscanf(fin, "%c%s", &ch, A);
fscanf(fin, "%c%s", &ch, B);
// cout << A << " " << B << "\n";
N = strlen(A);
M = strlen(B);
memset(nextA, -1, sizeof(nextA));
memset(nextB, -1, sizeof(nextB));
memset(C, 0, sizeof(C));
for (int i = N - 1; i >= 0; i--)
for (int j = 0; j < 26; j++)
if (A[i] == j + 'A')
nextA[i][j] = i;
else
nextA[i][j] = nextA[i + 1][j];
for (int i = M - 1; i >= 0; i--)
for (int j = 0; j < 26; j++)
if (B[i] == j + 'A')
nextB[i][j] = i;
else
nextB[i][j] = nextB[i + 1][j];
for (int i = N - 1; i >= 0; i--)
for (int j = M - 1; j >= 0; j--)
if (A[i] == B[j])
C[i][j] = C[i + 1][j + 1] + 1;
else
C[i][j] = C[i + 1][j] > C[i][j + 1] ? C[i + 1][j] : C[i][j + 1];
int i = 0, j = 0, ok = 1;
while (ok)
{
ok = 0;
for (int k = 25; k >= 0 && !ok; k--)
if (nextA[i][k] != -1 && nextB[j][k] != -1)
{
if (C[nextA[i][k]][nextB[j][k]] < K) continue;
fprintf(fout, "%c", k + 'A');
i = nextA[i][k] + 1;
j = nextB[j][k] + 1;
ok = 1;
}
K--;
}
fprintf(fout, "\n");
}
fclose(fin);
fclose(fout);
return 0;
}