Cod sursa(job #316394)

Utilizator FlorianFlorian Marcu Florian Data 19 mai 2009 14:07:11
Problema Seif Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.23 kb
#include<cstdio>
#include<string>
using namespace std;
#define MAX_N 1024
int T, N,M;
int bst[MAX_N][MAX_N];
char A[MAX_N], B[MAX_N];
int K;
int pi[32][MAX_N], pj[32][MAX_N];
inline int max(int a, int b) {return a>b?a:b; }
int main()
{
	freopen("seif.in","r",stdin);
	freopen("seif.out","w",stdout);
	int i,j,c,ok;
	scanf("%d\n",&T);
	while(T--)
	{
		scanf("%d\n",&K);
		memset(bst,0,sizeof(bst));
		scanf("%s\n",A+1);
		scanf("%s\n",B+1);
		N = strlen(A+1); M = strlen(B+1);
		for(i=N;i>0;--i)
			for(j=M;j>0;--j)
				bst[i][j] = A[i]==B[j]? bst[i+1][j+1] + 1: max(bst[i+1][j],bst[i][j+1]);
		memset(pi,-1,sizeof(pi)); memset(pi,-1,sizeof(pj));
		for(c = 0; c<26;++c)
		{
			for(i = N; i>0; --i)
				if(A[i] == (char)('A' + c)) pi[c][i] = i;
				else pi[c][i] = pi[c][i+1];
			for(i = M; i>0; --i)
				if(B[i] == (char)(c+'A')) pj[c][i] = i;
			else pj[c][i] = pj[c][i+1];
		}
		i = 1; j = 1; ok = 1;
		while(ok)
		{
			ok = 0;
			for(c=25;c>=0 && !ok;--c)
			{
				if(pi[c][i] != -1 && pj[c][j] != -1 && bst[pi[c][i]][pj[c][j]] >= K)
				{
					printf("%c",c+'A');
					ok = 1;
					i = pi[c][i]+1;
					j = pj[c][j]+1;
					break;
				}
			}
            K--;
		}
		printf("\n");
	}
	return 0;
}