Cod sursa(job #138669)

Utilizator gabitzish1Gabriel Bitis gabitzish1 Data 18 februarie 2008 23:28:09
Problema Seif Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.42 kb
#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;
}