fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int dp[3005][3005];
  5.  
  6. string backtrack(string s , string t){
  7.     ll i = s.size();
  8.     ll j = t.size();
  9.     string lcs = "";
  10.     while(i > 0 and j > 0){
  11.         if (s[i - 1] == t[j - 1]){
  12.             lcs+= s[i - 1];
  13.             i--;
  14.             j--;
  15.         }
  16.         else if (dp[i - 1][j] > dp[i][j - 1]){
  17.             i--;
  18.         }
  19.         else{
  20.             j--;
  21.         }
  22.     }
  23.     reverse(lcs.begin() , lcs.end());
  24.     return lcs;
  25. }
  26.  
  27. void solve() {
  28.     string s, t;
  29.     cin >> s >> t;
  30.     int n = s.size(), m = t.size();
  31.  
  32.     // DP bottom-up
  33.     for (int i = 0; i < n; i++) {
  34.         for (int j = 0; j < m; j++) {
  35.             if (s[i] == t[j]) {
  36.                 dp[i+1][j+1] = dp[i][j] + 1;
  37.             } else {
  38.                 dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
  39.             }
  40.         }
  41.     }
  42.  
  43.     // In ra LCS
  44.     cout << backtrack(s, t) << '\n';
  45. }
  46.  
  47. int main() {
  48.     ios::sync_with_stdio(0); cin.tie(0);
  49.     solve();
  50. }
  51.  
Success #stdin #stdout 0.01s 5268KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/qBBAqq
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
8 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!