fork(1) download
copy 
  1. #include <iostream>
  2. #include <string>
  3. using namespace std;
  4.  
  5. // Space optimized function to find length of Longest Common Subsequence
  6. // of substring X[0..m-1] and Y[0..n-1]
  7. int LCSLength(const string& X, const string& Y)
  8. {
  9. 	int m = X.length(), n = Y.length();
  10. 	if (m == 0 || n == 0) {
  11. 		return 0;
  12. 	}
  13.  
  14. 	/// TODO: swap X and Y if m < n.
  15.  
  16. 	// allocate storage for one-dimensional array curr
  17. 	int curr[n + 1] = {0};
  18.  
  19. 	// fill the lookup table in bottom-up manner
  20. 	for (int i = 1; i <= m; i++)
  21. 	{
  22. 	    //int prev2 = curr[0], prev = curr[0];
  23. 	    int prev2 = 0, prev = 0;
  24. 	    char ch = X[i - 1];
  25. 		for (int j = 1; j <= n; j++)
  26. 		{
  27. 		    int backup = curr[j], last;
  28. 			// if current character of X and Y matches
  29. 			if (ch == Y[j - 1])
  30. 				last = prev2 + 1;
  31.  
  32. 			// else if current character of X and Y don't match
  33. 			else
  34. 				last = max(backup, prev);
  35.  
  36. 			curr[j] = last;
  37. 			prev2 = backup;
  38. 			prev = last;
  39. 		}
  40. 	}
  41.  
  42. 	// LCS will be last entry in the lookup table
  43. 	return curr[n];
  44. }
  45.  
  46. // main function
  47. int main()
  48. {
  49. 	string X = "XMJYAUZ", Y = "MZJAWXU";
  50.  
  51. 	if (X.length() > Y.length())
  52. 		cout << "The length of LCS is " << LCSLength(X, Y);
  53. 	else
  54. 		cout << "The length of LCS is " << LCSLength(Y, X);
  55.  
  56. 	return 0;
  57. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 


			

					
			
			

				
	
		
		
	
		
		 stdout
					

				
				 copy
			

			
	

		
The length of LCS is 4

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/YUxTFY
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
6 years 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!