fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define LL long long
  5.  
  6. string a,b,c;
  7. int n1,n2,n3;
  8. LL dp[61][61][61];
  9.  
  10. LL f(int i,int j,int k){
  11. 	if(i==n1 && j==n2){
  12. 		if(k==n3){return 1;}
  13. 		else{return 0;}
  14. 	}
  15. 	if(k==n3){return 1;}	
  16. 	if(dp[i][j][k]!=-1){return dp[i][j][k];}
  17.  
  18. 	LL sum = 0;
  19. 	if(i<n1){
  20. 		if(a[i]==c[k]){
  21. 			sum = sum + f(i+1,j,k+1);
  22. 			if(j<n2){sum = sum + f(i+1,j+1,k+1);}
  23. 		}
  24. 		sum = sum + f(i+1,j,k);
  25. 	}
  26. 	if(j<n2){
  27. 		if(b[j]==c[k]){
  28. 			sum = sum + f(i,j+1,k+1);
  29. 			if(i<n1){sum = sum + f(i+1,j+1,k+1);}
  30. 		}
  31. 		sum = sum + f(i,j+1,k);
  32. 	}
  33. 	if(i<n1 && j<n2){
  34. 		sum = sum + f(i+1,j+1,k);
  35. 	}
  36. 	dp[i][j][k] = sum;
  37. 	return sum;
  38. }
  39.  
  40. int main(){
  41. 	#ifndef ONLINE_JUDGE
  42. 	freopen("input.in","r",stdin);
  43. 	freopen("output.out","w",stdout);
  44. 	#endif
  45.  
  46. 	int t;
  47. 	cin>>t;
  48.  
  49. 	while(t--){
  50. 		cin>>a>>b>>c;
  51. 		//cout<<a<<" "<<b<<" "<<c<<endl;
  52. 		n1 = a.length();n2 = b.length();n3 = c.length();
  53. 		memset(dp,-1,sizeof(dp));
  54. 		LL ans = f(0,0,0);
  55. 		cout<<ans<<endl;
  56. 	}
  57. }
Success #stdin #stdout 0s 17016KB
comments (?)
stdin
copy 
3
abc abc abc
aa aa aa
abbcd bccde abcde
stdout
copy 
408
66
9840
https://ideone.com/S9dALT
language:
C++ (gcc 8.3)
created:
7 years ago
visibility:
secret

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!