Cod sursa(job #331444)

Utilizator AndreiDDiaconeasa Andrei AndreiD Data 14 iulie 2009 00:30:40
Problema Seif Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <cstdio>
#include <cstring>

#define file_in "seif.in"
#define file_out "seif.out"

#define Nmax 1111

int n,m;
int i,j;
int d[Nmax][Nmax];
int p1[Nmax][26];
int p2[Nmax][26];
char a[Nmax];
char b[Nmax];
int T,K,c;

inline int max(int a, int b) { return a>b?a:b; }


int main()
{
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);

	scanf("%d", &T);

	while(T--)
	{
		scanf("%d", &K);

		scanf("%s",a);
		n=strlen(a);
		scanf("%s", b);
		m=strlen(b);

		//solve

		memset(d,0,sizeof(d));
		
		for (i=n-1;i>=0;--i)
			 for (j=m-1;j>=0;--j)
				  if (a[i]==b[j])
					   d[i][j]=d[i+1][j+1]+1;
				  else
					  d[i][j]=max(d[i+1][j],d[i][j+1]);

		memset(p1,-1,sizeof(p1));
		memset(p2,-1,sizeof(p2));
		
		for (i=n-1;i>=0;--i)
			 for (j=0;j<26;++j)
				  if (a[i]==j+'A')
 	                   p1[i][j]=i;
				  else 
					   p1[i][j]=p1[i+1][j];
		
		for (i=m-1;i>=0;--i)
			 for (j=0;j<26;++j)
				  if (b[i]==j+'A')
 	                   p2[i][j]=i;
				  else 
					   p2[i][j]=p2[i+1][j];		

		
        for (i=0,j=0;i<n && j<m;)   
        {   
            for (c=25;c>=0;--c)   
            {   
                if (p1[i][c]==-1 || p2[j][c]==-1) 
					continue;   
                if (d[p1[i][c]][p2[j][c]]<K) 
					continue;   
                printf("%c", c+'A');   
                i=p1[i][c]+1;
				j=p2[j][c]+1;
				--K;   
                break;   
            }   
        if (c==-1) break;   
        }   
        printf("\n");   
			  
				  
	}

	fclose(stdin);
	fclose(stdout);

	return 0;
}