fork download
copy 
  1. #include <bits/stdc++.h> 
  2. using namespace std;  
  3.  
  4. typedef long long ll;  
  5. typedef pair<int, int> ii;  
  6.  
  7. const int INF = 1e9;  
  8. const int N = 3e3 + 5;  
  9.  
  10. int n, m; 
  11. string s, t; 
  12. int dp[N][N]; // dp[i][j] là độ dài xâu con chung dài nhất khi xét các kí tự từ 1..i của xâu s 
  13. 			  // và các kí tự từ 1..j của xâu t  
  14.  
  15. // đáp án: dp[n][m] với n là độ dài xâu S, m là độ dài xâu T 
  16.  
  17. int main() {
  18. 	ios::sync_with_stdio(0); cin.tie(0);  	
  19. 	cin >> s; 
  20. 	cin >> t; 
  21.  
  22. 	n = s.size();    
  23. 	m = t.size(); 
  24.  
  25. 	s = ' ' + s;   
  26. 	t = ' ' + t;  
  27.  
  28.  	// get về
  29. 	for (int i = 1; i <= n; i++) {
  30. 		for (int j = 1; j <= m; j++) {
  31. 			if (s[i] == t[j]) {
  32. 				dp[i][j] = dp[i - 1][j - 1] + 1; // xâu con chung của đoạn 1..(i-1), 1..(j-1) của s và t 
  33. 												 // bổ sung thêm kí tự chung s[i]
  34. 			}
  35. 			else { // s[i] != t[j] 
  36. 				dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]); // xem xét là bỏ đi kí tự thứ i của s, 
  37. 															// hoặc bỏ đi kí tự thứ j của t
  38. 			}
  39. 		}
  40. 	} 
  41.  
  42. 	// cout << dp[n][m] << '\n';  
  43.  
  44. 	// update lên 
  45. 	// for (int i = 0; i <= n; i++) {
  46. 	// 	for (int j = 0; j <= m; j++) dp[i][j] = -INF;  
  47. 	// }
  48. 	// dp[0][0] = 0;  
  49.  
  50. 	// for (int i = 0; i <= n; i++) {
  51. 	// 	for (int j = 0; j <= m; j++) {
  52. 	// 		if (i + 1 <= n && j + 1 <= m && s[i + 1] == t[j + 1]) {
  53. 	// 			dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1);  
  54. 	// 		}
  55. 	// 		else {
  56. 	// 			if (i + 1 <= n) dp[i + 1][j] = max(dp[i + 1][j], dp[i][j]);   
  57. 	// 			if (j + 1 <= m) dp[i][j + 1] = max(dp[i][j + 1], dp[i][j]); 
  58. 	// 		}
  59. 	// 	}
  60. 	// }
  61.  
  62. 	// cout << dp[n][m] << '\n'; 
  63.  
  64. 	// trace 
  65. 	int i = n, j = m;   
  66. 	string ans = "";  
  67. 	while (true) {
  68. 		if (i == 0 || j == 0) break;
  69.  
  70. 		if (s[i] == t[j]) {
  71. 			ans += s[i];   
  72. 			i = i - 1, j = j - 1; 
  73. 		} 
  74. 		else {
  75. 			if (dp[i - 1][j] > dp[i][j - 1]) {
  76. 				i = i - 1; 
  77. 			}
  78. 			else {
  79. 				j = j - 1; 
  80. 			}
  81. 		}
  82. 	}
  83.  
  84. 	reverse(ans.begin(), ans.end());    
  85.  
  86. 	cout << ans << '\n'; 
  87. }
Success #stdin #stdout 0s 5300KB
comments (?)
stdin
copy 
abracadabra
avadakedavra
stdout
copy 
aaadara
https://ideone.com/MlUIdc
language:
C++14 (gcc 8.3)
created:
1 year 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!