fork download
copy 
  1. #include <stdio.h>
  2. #define FIN "cmlsc.in"
  3. #define FOUT "cmlsc.out"
  4. #define maxsize 1024
  5.  
  6. typedef unsigned int u;
  7.  
  8. u max(u a, u b) {
  9.       if(a > b) return a;
  10.            else return b;
  11. }
  12.  
  13. //global
  14. u X[maxsize], 
  15.   Y[maxsize], 
  16.   ans[maxsize], 
  17.   matLCS[maxsize][maxsize], 
  18.   n, m;
  19.  
  20. u createMatrix() {
  21.  
  22.   for(u i = 1; i <= n; ++i) {
  23.  
  24.   	for(u j = 1; j <= m; ++j) {
  25.  
  26.   		if(X[i] == Y[j]) {
  27.  
  28.   		   matLCS[i][j] = 1 + matLCS[i-1][j-1];
  29.  
  30.   		} else {
  31.  
  32.   		   matLCS[i][j] = max(matLCS[i][j-1], matLCS[i-1][j]);
  33.   		}
  34.     }		
  35.  
  36.   }  
  37.  
  38.   return matLCS[n][m];
  39. }  
  40.  
  41. void createSubseq(u i, u j) {
  42.  
  43.      if(i == 0 || j == 0) return;
  44.  
  45.      if(X[i] == Y[j]) {
  46.  
  47.         createSubseq(i - 1, j - 1);          
  48.  
  49.      	printf("%d ", X[i]);
  50.  
  51.      } else {
  52.  
  53.      	if(matLCS[i][j-1] < matLCS[i-1][j]) {
  54.  
  55.      	   createSubseq(i - 1, j);
  56.  
  57.         } else {
  58.  
  59.            createSubseq(i, j - 1);         
  60.  
  61.         } 
  62.      }   
  63.  
  64. }
  65.  
  66. int main(int argc, char const *argv[])
  67. {
  68. 	//freopen(FIN, "r", stdin); 
  69. 	//freopen(FOUT, "w", stdout); 
  70.  
  71. 	scanf("%d %d", &n, &m);
  72.  
  73. 	for(u i = 1; i <= n; ++i) {
  74. 		scanf("%d", &X[i]);
  75. 	}
  76. 	for(u j = 1; j <= m; ++j) {
  77. 		scanf("%d", &Y[j]);
  78. 	}	
  79.  
  80. 	printf("%d\n", createMatrix());
  81.  
  82. 	createSubseq(n, m);
  83. 	return 0;
  84. }
Success #stdin #stdout 0s 4180KB
comments (?)
stdin
copy 
8 5
2 4 3 7 3 9 8 1
4 7 5 8 1
stdout
copy 
4
4 7 8 1
https://ideone.com/sfThv1
Longest Common Subsequence in C using recursion.
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!