fork download
copy 
  1. #include <iostream>
  2. #define FIN "cmlsc.in"
  3. #define FOUT "cmlsc.out"
  4. #define DIM 1024
  5. #define max(a,b) ((a > b) ? a : b)
  6. #define FOR(i,a,b) for(i=a;i<=b;++i)
  7.  
  8. typedef unsigned int u;
  9.  
  10. u X[DIM], Y[DIM], Answer[DIM], LCS[DIM][DIM], n, m, i, j, k;
  11.  
  12. int main(int argc, char const *argv[])
  13. {
  14. 	//freopen(FIN, "r", stdin);
  15. 		//freopen(FOUT, "w", stdout);
  16.  
  17. 	std::cin>>n>>m;
  18.  
  19.     FOR(i, 1, n) std::cin>>X[i];
  20.         FOR(j, 1, m) std::cin>>Y[j];
  21.  
  22.         	FOR(i,1,n)
  23.         		FOR(j,1,m)
  24.         			if(X[i] == Y[j]) LCS[i][j] = 1 + LCS[i-1][j-1];
  25.         		                else 
  26.         		                	 LCS[i][j] = max(LCS[i][j-1], LCS[i-1][j]);
  27.     std::cout<<LCS[n][m]<<"\n";
  28.  
  29. 	i = n; j = m;
  30.  
  31.     while(i!=0 && j!=0) {
  32.     	 if(X[i] == Y[j]) {
  33.     	 	Answer[++k] = X[i];
  34.     	 	i--;j--;
  35.     	 } else {
  36.     	 	if(LCS[i][j-1] < LCS[i-1][j]) i--;
  37.     	 	                  else j--;
  38.     	 }
  39.     }
  40.  
  41.     for(i = k; i != 0; i--) std::cout<<Answer[i]<<" ";
  42.  
  43. 	return 0;
  44. }
Success #stdin #stdout 0s 4420KB
comments (?)
stdin
copy 
5 4
1 7 3 5 8
7 5 8 1
stdout
copy 
3
7 5 8
https://ideone.com/kf02K5
Longest Common Subsequence in c++ using macros FOR
language:
C++ (gcc 8.3)
created:
4 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!