fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll   long long int
  3. #define pb push_back
  4. #define ff first
  5. #define ss second
  6. #define mp make_pair
  7. #define inf 100000000000000LL
  8. #define fast_io	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
  9. #define mod 1000000007 
  10. #define range 1000000
  11. #define lg 22
  12. #define range2 1000000000
  13. #define pp pair<ll,ll>
  14. //#define endl "\n"
  15.  
  16.  
  17. using namespace std;
  18. string s1,s2;
  19. ll dp[5001][5001][2][2];
  20. //ll dp[p1][p2][f][k]-> p1, p2 is index of string s1,s2 respectcivegly, f-> 0 matlab abhi tak ek bhi add nhi kiya char-> 1 matlab ek daal diya // aur 1 daalna zaruri h. k-> [0]->max length ab tak, [1] -> uska count ab tak
  21.  
  22.  
  23. pp calc(ll p1,ll p2,ll f)		//returns (new_max_len,count)
  24. {
  25.  
  26.  
  27. 	if(p1==-1||p2==-1)
  28. 	{
  29. 		pp x;
  30. 		x.ff=0,x.ss=0; // by default if boo criteria satisfy toh count and len 0,
  31.  
  32. 		if(f==1) // agar ek char daal liya toh count=1 return //self explanatory
  33. 		x= mp(0,1);
  34. 		else
  35. 		if(p1==-1&&p2!=-1) // manlo ki s1 khatam ho gya , par s2 k kuch character bache h-> aur f=0 h, toh ek char add kr skte h-> one of any of those left hence count= p2+1, max_len=1 coz 1 char le liya LCS mein
  36. 			x= mp(1,p2+1);
  37.  
  38. 		return x;
  39. //		cout<<p1<<" "<<p2<<" "<<f<<"	"<<x.ff<<" "<<x.ss<<endl;
  40.  
  41.  
  42. 	}
  43. 	if(dp[p1][p2][f][1]!=-1)
  44. 	return mp(dp[p1][p2][f][0],dp[p1][p2][f][1]);
  45. 	pp x1,x2,x3,ans;
  46. 	ll xn;	
  47.  
  48. 	x1.ff=x2.ff=x3.ff=ans.ff=0;
  49. 	x1.ss=x2.ss=x3.ss=ans.ss=0;
  50. 	if(s1[p1]==s2[p2])
  51. 	{
  52. 		x1=calc(p1-1,p2-1,f); // normal jaisa hota same h toh length+1
  53. 		x1.ff++;
  54.  
  55. 		if(f<1) // special case// agar naya char s1 ke p1 k right mein daal diya aur use aur s2[p2] ko le lia
  56. 		{
  57. 			x2=calc(p1,p2-1,f+1);// toh p1 vaisa hi rahega, p2-1 ho jaega
  58. 			x2.ff++; // coz humne s2[p2] ko match kara diya inserted char se toh length+1 ho gyi
  59. 		}
  60.  
  61.  
  62.  
  63. 		xn=max(x1.ff,x2.ff); // max length ab tak kitni h?
  64. 		ans.ff=xn;
  65. 		// jis jis ki uske equal h, unke counts add karlo
  66. 		if(xn==x1.ff)
  67. 		ans.ss+=x1.ss;
  68.  
  69. 		if(xn==x2.ff)
  70. 		ans.ss+=x2.ss;
  71.  
  72. 	}
  73. 	else
  74. 	{
  75. 		x1=calc(p1-1,p2,f); // normal
  76. 		x2=calc(p1,p2-1,f); // normal
  77.  
  78. 		if(f<1) // special case// agar naya char s1 ke p1 k right mein daal diya aur use aur s2[p2] ko le lia
  79. 		{
  80. 			x3=calc(p1,p2-1,f+1); // toh p1 vaisa hi rahega, p2-1 ho jaega
  81. 			x3.ff++; // coz humne s2[p2] ko match kara diya inserted char se toh length+1 ho gyi
  82. 		}
  83. 		// max length ab tak kitni h?
  84.  
  85. 		xn=max(x1.ff,max(x2.ff,x3.ff));
  86. 		ans.ff=xn;
  87.  
  88. 		// jis jis ki uske equal h, unke counts add karlo
  89.  
  90. 		if(xn==x1.ff)
  91. 		ans.ss+=x1.ss;
  92.  
  93. 		if(xn==x2.ff)
  94. 		ans.ss+=x2.ss;
  95.  
  96. 		if(xn==x3.ff)
  97. 		ans.ss+=x3.ss;
  98. //		cout<<xn<<endl;
  99. //		cout<<p1<<" "<<p2<<" "<<f<<"	x1	"<<x1.ff<<" "<<x1.ss<<endl;
  100. //		cout<<p1<<" "<<p2<<" "<<f<<"	x2	"<<x2.ff<<" "<<x2.ss<<endl;
  101. //		cout<<p1<<" "<<p2<<" "<<f+1<<"	x3	"<<x3.ff<<" "<<x3.ss<<endl;
  102. //		cout<<p1<<" "<<p2<<" "<<f<<"	x4	"<<ans.ff<<" "<<ans.ss<<endl;
  103. 	}
  104. //	cout<<p1<<" "<<p2<<" "<<f<<"	"<<ans.ff<<" "<<ans.ss<<endl;
  105. 	// inka pair bana k store karlo
  106. 	dp[p1][p2][f][0]=ans.ff;
  107. 	dp[p1][p2][f][1]=ans.ss;
  108.  
  109. 	return mp(ans.ff,ans.ss);
  110.  
  111. }
  112.  
  113.  
  114. int main()
  115. {
  116. 	ll n1,n2;
  117. 	memset(dp,-1,sizeof(dp));
  118. 	cin>>s1>>s2;
  119. 	n1=s1.length()-1;
  120. 	n2=s2.length()-1;
  121. 	pp x=calc(n1,n2,0);
  122. //	cout<<x.ff<<"	"<<x.ss<<endl;
  123. 	cout<<x.ss<<endl;
  124.  
  125.  
  126. }
Success #stdin #stdout 0.2s 785216KB
comments (?)
stdin
copy 
zzz
azzzz
stdout
copy 
5
https://ideone.com/5mt9wN
language:
C++14 (clang 8.0)
created:
4 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!