fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. #define int long long
  4. int f[3005][3005];
  5. signed main(){
  6.     string s,t;
  7.     cin >> s >> t;
  8.     int n = s.size(), m = t.size();
  9.     s = " " + s;
  10.     t = " " + t;
  11.     for(int i = 1; i <= n; i++){
  12.         for(int j = 1; j <= m; j++){
  13.             f[i][j] = max(f[i-1][j], f[i][j-1]);
  14.             if(s[i] == t[j]) f[i][j] = max(f[i][j], f[i-1][j-1] + 1);
  15.         }
  16.     }
  17.     int i = n, j = m;
  18.     string ans;
  19.     while(i > 0 && j > 0){
  20.         if(s[i] == t[j]){
  21.             ans += s[i];
  22.             i--, j--;
  23.         }
  24.         else if(f[i-1][j] >= f[i][j-1]) i--;
  25.         else j--;
  26.     }
  27.  
  28.     reverse(ans.begin(), ans.end());
  29.     cout << ans << "\n";
  30.     return 0;
  31. }
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/us3CdT
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

						
created:
								
						
5 hours 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!