fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. #pragma GCC optimize ("O3") // Optimization directive for GCC
  6.  
  7. #define ios cin.tie(0), ios::sync_with_stdio(false) // Speeds up I/O
  8.  
  9. // Global declaration of dp and prestate. This is generally not recommended for large
  10. // arrays due to potential stack overflow, but for competitive programming with
  11. // limits like 3005, it might be intended for static allocation in the data segment.
  12. // However, 'n' and 'm' are not defined at this scope, so this will cause a compilation error.
  13. // These should be declared inside main after reading n and m.
  14. // vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0)); // Error: n and m not defined
  15. // pair<int, int> prestate[3005][3005]; // This is okay as a global with fixed size
  16.  
  17. signed main(){
  18. 	ios;
  19. 	string s, s2;
  20. 	cin >> s >> s2;
  21. 	int n = s.size();
  22. 	int m = s2.size();
  23.  
  24. 	// Declare dp and prestate here after n and m are known.
  25. 	vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
  26. 	pair<int, int> prestate[3005][3005]; // Assuming max size 3000 for strings
  27.  
  28. 	s = " " + s;
  29. 	s2 = " " + s2;
  30.  
  31.  
  32. 	for(int i = 1; i <= n; i++){
  33. 		for(int j = 1; j <= m; j++){
  34. 			if(s[i] == s2[j]){
  35. 				dp[i][j] = dp[i - 1][j - 1] + 1;
  36. 				prestate[i][j] = {i - 1, j - 1};
  37. 			}else{
  38. 				if(dp[i][j - 1] > dp[i - 1][j]){
  39. 				    dp[i][j] = dp[i][j - 1];
  40. 				    prestate[i][j] = {i, j - 1};
  41. 				}else{
  42. 				    dp[i][j] = dp[i - 1][j];
  43. 				    prestate[i][j] = {i - 1, j};
  44. 				}
  45. 			}
  46. 		}
  47. 	}
  48.  
  49. 	string ans = "";
  50. 	// Reconstruction loop.
  51. 	// The condition `while(n != 0 || m != 0)` is mostly correct for tracing back
  52. 	// to the base case (0, 0).
  53. 	// However, the logic inside has issues.
  54. 	int cur_n = n; // Use different variable names to avoid shadowing
  55. 	int cur_m = m;
  56. 	while(cur_n > 0 || cur_m > 0){ // Continue as long as we are not at (0,0)
  57. 		// The condition `if(s[n] == s[m])` is incorrect. It should compare
  58. 		// characters from the original strings `s` and `s2` at the current indices `cur_n` and `cur_m`.
  59. 		// Also, the character should only be added to the answer when the move was a diagonal one (indicating a match).
  60.  
  61. 		if(prestate[cur_n][cur_m].first == cur_n - 1 && prestate[cur_n][cur_m].second == cur_m - 1){
  62. 			// This indicates a diagonal move, meaning s[cur_n] == s2[cur_m] was true in the DP step.
  63. 			ans += s[cur_n]; // Append the character that was part of the LCS
  64. 			// cout << s[cur_n]; // Printing here will print in reverse order
  65. 		}
  66.  
  67. 		// Move to the previous state based on prestate
  68. 		int prevn = prestate[cur_n][cur_m].first;
  69. 		int prevm = prestate[cur_n][cur_m].second;
  70. 		cur_n = prevn; // Update current indices
  71. 		cur_m = prevm;
  72.  
  73. 		// The lines `int n = prevn; int m = prevm;` inside the loop
  74. 		// declare new local variables `n` and `m` that shadow the outer `n` and `m`.
  75. 		// This is incorrect and the loop condition should use the updated `cur_n` and `cur_m`.
  76. 	}
  77.  
  78. 	// The LCS is built in reverse order, so reverse it.
  79. 	reverse(ans.begin(), ans.end());
  80.  
  81. 	cout << ans << endl;
  82.  
  83. 	return 0;
  84. }
Success #stdin #stdout 0.02s 74120KB
comments (?)
stdin
copy 
axyb
abyxb
stdout
copy 
axb
https://ideone.com/606apn
language:
C++14 (gcc 8.3)
created:
2 days 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!