fork download
copy 
  1. #include <bits/stdc++.h>
  2. int main(){
  3.     std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr);
  4.     std::string a, b;
  5.     std::cin >> a >> b;
  6.     int n = (int)a.size();
  7.     int m = (int)b.size();
  8.     int dp[n+1][m+1];
  9.     for(int i=0; i<=n; ++i)
  10.         dp[i][0] = 0;
  11.     for(int j=0; j<=m; ++j)
  12.         dp[0][j] = 0;
  13.     for(int i=1; i<=n; ++i)
  14.         for(int j=1; j<=m; ++j){
  15.             dp[i][j] = 0;
  16.             // take
  17.             if(a[i-1] == b[j-1])
  18.                 dp[i][j] = dp[i-1][j-1]+1;
  19.             // leave
  20.             dp[i][j] = std::max(dp[i][j], dp[i][j-1]);
  21.             dp[i][j] = std::max(dp[i][j], dp[i-1][j]);
  22.         }
  23.     std::string ans;
  24.     int i = n, j = m;
  25.     while(dp[i][j]) {
  26.         if (dp[i - 1][j] == dp[i][j])
  27.                 --i;
  28.         else if (dp[i][j - 1] == dp[i][j])
  29.                 --j;
  30.         else{
  31.             --i;
  32.             --j;
  33.             ans.push_back(a[i]);
  34.         }
  35.     }
  36.     std::reverse(ans.begin(), ans.end());
  37.     std::cout << ans << '\n';
  38. }
Success #stdin #stdout 0.01s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/8zDWbo
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++14 (gcc 8.3)

					

					

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