fork(5) download
copy 
  1. //DP_LongestCommonSubStringv2.cpp
  2. /*
  3. 	author: ayusofayush
  4. 	follow: @Hitman47
  5. 	topic : Longest Common Substring with substring printed.
  6. 	tc: O(m*n) and space: O(n)
  7. 	along with substring printing
  8. */
  9. #include<bits/stdc++.h>
  10. #define ll long long
  11. #define fast ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
  12. using namespace std;
  13.  
  14. string LCS(string x,string y,int n,int m)
  15. {
  16. 	int dp[2][m+1];
  17. 	memset(dp,0,sizeof dp);
  18.  
  19. 	int b,mxlen=0,end=0;
  20. 	for(int i=1;i<=n;i++){
  21. 		b = i&1;
  22. 		for(int j=1;j<=m;j++)
  23. 		{
  24. 			if(x[i-1]==y[j-1])
  25. 			{
  26. 				dp[b][j] = dp[1-b][j-1]+1;
  27. 				if(mxlen < dp[b][j])
  28. 				{
  29. 					mxlen = dp[b][j];
  30. 					end = i;
  31. 				}
  32. 			}
  33. 		}
  34. 	}
  35. 	return x.substr(end-mxlen,mxlen);
  36. }
  37.  
  38. int main()
  39. {	
  40. 	string x="AforApple",y="for";
  41. 	int n = x.length(), m = y.length();
  42. 	cout<<LCS(x,y,n,m);	
  43.  
  44. 	return 0;
  45. }
Success #stdin #stdout 0s 15240KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
for
https://ideone.com/tfhY6P
language:
C++14 (gcc 8.3)
created:
5 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!