fork(1) download
copy 
  1. #include<stdio.h>
  2. #include<iostream>
  3. #include<math.h>
  4. #include<string.h>
  5. #include<string>
  6. #include<stdlib.h>
  7. #include<map>
  8. #include<vector>
  9. #include<queue>
  10. #include<stack>
  11. #include<algorithm>
  12. #include<set>
  13. using namespace std;
  14.  
  15. // Define Some Variables
  16. #define eps 1e-14
  17. #define si 105
  18. #define pi acos(-1.0)
  19. #define inf (1<<30)-1
  20. #define mod 1000000000 //10^9
  21.  
  22. //Define Some Functions
  23. #define even(a) ((a)%2==0)
  24. #define odd(a) ((a)%2==1)
  25. #define max(a,b) (a>b ?a:b)
  26. #define min(a,b) (a<b ?a:b)
  27. #define sqr(a)((a)*(a))
  28. #define area(x1,y1,x2,y2,x3,y3) (x1*(y2-y3)+x2*(y3-y1)+x3*(y1-y2)) //Area of a triangle
  29. #define dist(x1,y1,x2,y2) (sqr(x1-x2)+sqr(y1-y2)) //Distance between two points
  30. #define mem(a,v) memset(a,v,sizeof(a))
  31. inline bool compare( double a, double b ) { return fabs( a-b ) < 1e-9 ; }
  32. #define fr(i,a,b) for(i=a;i<=b;i++)
  33. #define rep(i,a,b) for(i=a;i<b;i++)
  34. #define rev(i,a,b)  for(i=a;i>=b;i--)
  35.  
  36. typedef long long i64;
  37.  
  38. int dx[]={0,0,1,-1};
  39. int dy[]={1,-1,0,0};
  40. int i,j,l,n,cs=1,l1,l2;
  41. char ch1[si],ch2[si],res[si],dpc[si][si][si];
  42. int dp[si][si];
  43.  
  44. i64 bmod(i64 a,i64 b)
  45. {
  46.     if(b==0)
  47.         return 1;
  48.     i64 x=bmod(a,b/2);
  49.     x=(x*x)%mod;
  50.     if(b%2==1)
  51.         x=(x*a)%mod;
  52.     return x;
  53. }
  54.  
  55. int gcd(int a,int b)
  56. {
  57.     while(b>0)
  58.     {
  59.         a%=b;
  60.         a^=b;
  61.         b^=a;
  62.         a^=b;
  63.     }
  64.     return a;
  65. }
  66.  
  67.  
  68. i64 lcm(i64 a,i64 b)
  69. {
  70. 	return ((a*b)/gcd(a,b));
  71. }
  72.  
  73. int rec(int i,int j,char* res)
  74. {
  75.     if(i==l1||j==l2)
  76.     return 0;
  77.     int &ret=dp[i][j];
  78.     if(ret!=-1)
  79.     {
  80.         strcpy(res,dpc[i][j]);
  81.         return ret;
  82.     }
  83.  
  84.     int p,q,ll,x;
  85.     char st1[si],st2[si];
  86.     if(ch1[i]==ch2[j])
  87.     {
  88.         ret=1+rec(i+1,j+1,res);
  89.         st1[0]=ch1[i];
  90.         ll=strlen(res);
  91.         rep(x,0,ll)
  92.         st1[x+1]=res[x];
  93.         st1[ll+1]=0;
  94.         strcpy(res,st1);
  95.         strcpy(dpc[i][j],res);
  96.     }
  97.     else
  98.     {
  99.         strcpy(st2,res);
  100.  
  101.         p=rec(i+1,j,res);
  102.         strcpy(st1,res);
  103.  
  104.      //   strcpy(res,st2);
  105.         q=rec(i,j+1,st2);
  106.      //   strcpy(st2,res);
  107.  
  108.         if(p>q)
  109.         strcpy(res,st1);
  110.         else if(p<q)
  111.         strcpy(res,st2);
  112.         else
  113.         {
  114.             p=strcmp(st1,st2);
  115.             if(p<0)
  116.             strcpy(res,st1);
  117.             else
  118.             strcpy(res,st2);
  119.         }
  120.  
  121.         ret=max(p,q);
  122.         strcpy(dpc[i][j],res);
  123.     }
  124.     return ret;
  125. }
  126.  
  127. int main()
  128. {
  129. //	freopen("input.txt", "r", stdin);
  130. //	freopen("output.txt", "w", stdout);
  131.  
  132.     int t;
  133.     scanf("%d",&t);
  134.    	while(t--)
  135.    	{
  136.    	    scanf("%s%s",&ch1,ch2);
  137.    	    l1=strlen(ch1);
  138.    	    l2=strlen(ch2);
  139. 		mem(dp,-1);
  140. 		res[0]=0;
  141. 		int ans=rec(0,0,res);
  142. 		printf("Case %d: ",cs++);
  143. 		if(ans==0)
  144. 		puts(":(");
  145. 		else
  146.         puts(res);
  147.     }
  148.    	return 0;
  149. }
  150.  
Success #stdin #stdout 0s 4476KB
comments (?)
stdin
copy 
5
 
ab
ba
 
zxcvbn
hjgasbznxbzmx
 
you
kjhs

xhrvvyvqxvuiuatmzcieqdfsycblip
tojlrnpnvmjhrhgpahvvebvomgmagbknmjaoponcrawltsmsfhrnidvgxeiqrvtmthdqsgmisrfqzdqqmgmvt

abdzcc
azcbdc
stdout
copy 
Case 1: a
Case 2: zxb
Case 3: :(
Case 4: hrvvvamcieqdsi
Case 5: abdc
https://ideone.com/cCuqBo
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!