fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // Function to find Longest common substring of sequences X[0..m-1] and Y[0..n-1]
  5. string LCS(string X, string Y, int m, int n)
  6. {
  7. 	int maxlen = 0;			// max length of Longest common substring
  8. 	int endingIndex = m;	// ending index of Longest common substring in X
  9.  
  10. 	// lookup[i][j] stores the length of LCS of substring X[0..i-1], Y[0..j-1]
  11. 	int lookup[m + 1][n + 1];
  12.  
  13. 	// initialize all cells of lookup table to 0
  14. 	memset(lookup, 0, sizeof(lookup));
  15.  
  16. 	// fill the lookup table in bottom-up manner
  17. 	for (int i = 1; i <= m; i++)
  18. 	{
  19. 		for (int j = 1; j <= n; j++)
  20. 		{
  21. 			// if current character of X and Y matches
  22. 			if (X[i - 1] == Y[j - 1])
  23. 			{
  24. 				lookup[i][j] = lookup[i - 1][j - 1] + 1;
  25.  
  26. 				// update the maximum length and ending index
  27. 				if (lookup[i][j] > maxlen)
  28. 				{
  29. 					maxlen = lookup[i][j];
  30. 					endingIndex = i;
  31. 				}
  32. 			}
  33. 		}
  34. 	}
  35.  
  36. 	// return Longest common substring having length maxlen 
  37. 	return X.substr(endingIndex - maxlen, maxlen);
  38. }
  39.  
  40. // main function
  41. int main()
  42. {
  43. 	string X = "DABCD", Y = "BABCA";
  44. 	int m = X.length(), n = Y.length();
  45.  
  46. 	// Find Longest common substring
  47. 	cout << "The Longest common substring is " << LCS(X, Y, m, n);
  48.  
  49. 	return 0;
  50. }
  51.  
Success #stdin #stdout 0s 16064KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
The Longest common substring is ABC
https://ideone.com/dtjGkc
Longest common substring problem
language:
C++14 (gcc 8.3)
created:
6 years 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!