fork download
copy 
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <string>
  5. #include <set>
  6. #include <iomanip>
  7. #include <iterator>
  8. #include <cmath>
  9. #include <map>
  10. #include <string.h>
  11. #include <ctime>
  12. #include <queue>
  13. #include<unordered_map>
  14. #define ll long long
  15. #define endl '\n'
  16. using namespace std;
  17.  
  18. vector<int>dirx{ 0,1,-1,0,1,1,-1,-1 };
  19. vector<int>diry{ -1,0,0,1,1,-1,1,-1 };
  20.  
  21. bool valid(int n, int m, int x, int y) {
  22. 	return x >= 0 && y >= 0 && x < n&& y < m;
  23. }
  24.  
  25. ll gcd(ll a, ll b) {
  26. 	if (b == 0)
  27. 		return a;
  28. 	return gcd(b, a % b);
  29. }
  30. ll lcm(ll a, ll b) {
  31. 	return (a * b) / gcd(a, b);
  32. }
  33.  
  34.  
  35.  
  36. const int N = 3e3 + 5;
  37. const ll mod = 1e9 + 7;
  38. int inf = 1e9;
  39. map<pair<int, int>,string > dp;
  40. string s1, s2;
  41. int n, m;
  42. string lcm(int i, int j) {
  43. 	if (i == n || j == m)
  44. 		return "";
  45. 	if (dp.find({ i, j }) != dp.end())
  46. 		return dp[{i, j}];
  47. 	string& ret = dp[{i, j}];
  48. 	ret = "";
  49. 	if (s1[i] == s2[j])
  50. 		ret = s1[i] + lcm(i + 1, j + 1);
  51. 	else {
  52. 		string path1 = lcm(i + 1, j);
  53. 		string path2 = lcm(i, j + 1);
  54. 		if (path1.size() >= path2.size())
  55. 			ret = path1;
  56. 		else
  57. 			ret = path2;
  58. 	}
  59. 	return ret;	
  60. }
  61.  
  62. void solve() {
  63. 	cin >> s1 >> s2;
  64. 	n = s1.size(), m = s2.size();
  65. 	dp.clear();
  66. 	cout << lcm(0, 0) << endl;
  67. }
  68.  
  69. //void files() {
  70. //
  71. //	freopen("input.txt", "r", stdin);
  72. //	freopen("output.txt", "w", stdout);
  73. //}
  74.  
  75.  
  76. int main() {
  77. 	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  78. 	/*int t; cin >> t;
  79. 	while (t--)*/
  80. 	solve();
  81.  
  82.  
  83. 	return 0;
  84. }
Success #stdin #stdout 0.01s 5504KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/t8hqkE
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
1 year 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!