light oj An Easy LCS

1802 단어
#include <stdio.h>
#include <string.h>
#define maxx 150
char s1[maxx];
char s2[maxx];
int dp[maxx][maxx];
char s[maxx][maxx][maxx];
int main()
{
       int T;
       while( scanf("%d",&T)==1)
	   {
        int cases=0;
        while(T--)
        {
			memset(dp,0,sizeof(dp));
			memset(s,0,sizeof(s));
            int k;
            scanf("%s %s",s1+1,s2+1);
            int n=strlen (s1+1);
            int m=strlen (s2+1);

            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
            {
                if(s1[i]==s2[j])
                {
                    dp[i][j]=dp[i-1][j-1]+1;
                    for(k=0;k<dp[i-1][j-1];k++)
                        s[i][j][k]=s[i-1][j-1][k];
                    s[i][j][k]=s1[i];
                }
                  else
               {
                   if(dp[i-1][j]>dp[i][j-1])
                   {
                       dp[i][j]=dp[i-1][j];
                       strcpy(s[i][j],s[i-1][j]);
                   }
                   else if(dp[i][j-1]>dp[i-1][j])
                   {
                       dp[i][j]=dp[i][j-1];
                       strcpy(s[i][j],s[i][j-1]);
                   }
                   else
                   {
                       dp[i][j]=dp[i-1][j];
                       if(strcmp(s[i-1][j],s[i][j-1])>0)
                           strcpy(s[i][j],s[i][j-1]);
                       else
                           strcpy(s[i][j],s[i-1][j]);
                   }
               }
            }
		  //printf("%d
",n); printf("Case %d: ",++cases); if(dp[n][m]==0) printf(":(
"); else puts(s[n][m]); } } }

좋은 웹페이지 즐겨찾기