fork download
copy 
  1. // top down approach
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. void findStr(int i, int j, string x, string y, string sub_str, vector<vector<int>>&lookup)
  7. {
  8. 	if(i == 0 || j == 0)
  9. 	{
  10. 		reverse(sub_str.begin(), sub_str.end());
  11. 		cout<<sub_str<<endl;
  12. 		return;
  13. 	}
  14. 	if(x[i] == y[j])
  15. 	{
  16. 		sub_str += x[i];
  17. 		findStr(i - 1, j - 1, x, y, sub_str, lookup);
  18. 	}
  19. 	else
  20. 	{
  21. 		if(lookup[i][j - 1] > lookup[i - 1][j])
  22. 			findStr(i, j - 1, x, y, sub_str, lookup);
  23. 		else if(lookup[i][j - 1] < lookup[i - 1][j])
  24. 			findStr(i - 1, j, x, y, sub_str, lookup);
  25. 		else
  26. 		{
  27. 			findStr(i, j - 1, x, y, sub_str, lookup);
  28. 			findStr(i - 1, j, x, y, sub_str, lookup);
  29. 		}
  30. 	}
  31. }
  32.  
  33. void findString(int m, int n, string x, string y, vector<vector<int>>&lookup)
  34. {
  35. 	int i = m, j = n;
  36. 	string sub_str = "";
  37. 	findStr(i, j, x, y, sub_str, lookup);
  38. 	return;
  39. }
  40.  
  41. int lc_subsequence(int i, int j, string x, string y, vector<vector<int>>&lookup)
  42. {
  43. 	if(lookup[i][j] < INT_MAX)
  44. 		return lookup[i][j];
  45. 	if(x[i] == y[j])
  46. 		lookup[i][j] = 1 + lc_subsequence(i - 1, j - 1, x, y, lookup);
  47. 	else
  48. 	{
  49. 		lookup[i][j] = max(lc_subsequence(i - 1, j, x, y, lookup), lc_subsequence(i, j - 1, x, y, lookup));
  50. 	}
  51. 	return lookup[i][j];
  52. }
  53.  
  54. int memoized_top_down(string x, string y)
  55. {
  56. 	int m = x.length();
  57. 	int n = y.length();
  58. 	x = "a" + x;	// prefixed by some character for making index from 1
  59. 	y = "a" + y;
  60. 	vector<vector<int>>lookup(m+1, vector<int>(n+1));
  61. 	for(int i = 0; i <= m; i++)
  62. 	{
  63. 		for(int j = 0; j <= n; j++)
  64. 		{
  65. 			if(i == 0 || j == 0)
  66. 				lookup[i][j] = 0;
  67. 			else
  68. 				lookup[i][j] = INT_MAX;
  69. 		}
  70. 	}
  71. 	int ans = lc_subsequence(m, n, x, y, lookup);
  72. 	// print all possible subsequence
  73. 	findString(m, n, x, y, lookup);
  74. 	return ans;
  75. }
  76.  
  77. int main()
  78. {
  79. 	string x, y;
  80. 	cin>>x>>y;
  81. 	int ans = memoized_top_down(x, y);
  82. 	cout<<"length of largest subsequence : "<<ans<<endl;
  83. 	return 0;
  84. }
Success #stdin #stdout 0s 4496KB
comments (?)
stdin
copy 
qpqrr pqprqrp
stdout
copy 
pqrr
qprr
qpqr
qpqr
length of largest subsequence : 4
https://ideone.com/AV0kkF
language:
C++14 (gcc 8.3)
created:
3 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!