fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int A[1000007],B[10],C[1000008][11];
  4. int l1,l2,i,j;
  5. void lcs()
  6. {
  7.   memset(C,0,sizeof(C));
  8.   for(i=0;i<=l1;i++) {
  9.     for(j=0;j<=l2;j++) {
  10.       if(i==0 || j==0) {
  11.         C[i][j]=0;
  12.       }
  13.       else {
  14.             if(A[i-1]==B[j-1]) {
  15.             C[i][j]=C[i-1][j-1]+1;
  16.           }
  17.           else {
  18.             C[i][j]=max(C[i-1][j],C[i][j-1]);
  19.           }
  20.       }
  21.     }
  22.   }
  23.   int index=C[l1][l2];
  24.   if(index==0) {
  25.     printf("0\n");
  26.   }
  27.   else {
  28.     printf("%d ",index);
  29.   vector<int> S(index);
  30.   vector<int> :: iterator it;
  31.   i = l1, j = l2;
  32.    while (i > 0 && j > 0)
  33.    {
  34.       if (A[i-1] == B[j-1])
  35.       {
  36.           S[index-1] = A[i-1]; 
  37.           i--; j--; index--;     
  38.       }
  39.       else if (C[i-1][j] > C[i][j-1])
  40.            i--;
  41.         else if(C[i-1][j] < C[i][j-1])
  42.            j--;
  43.          else if(C[i-1][j] == C[i][j-1])
  44.          {
  45.             if(B[j-1]>A[i-1])
  46.               j--;
  47.             else
  48.               i--;
  49.          }
  50.      }
  51.  
  52.   for(it=S.begin();it!=S.end();it++) {
  53.     printf("%d ",*it);
  54.   }
  55.   S.clear();
  56.     printf("\n");
  57.    }
  58. }
  59.  
  60. int main ()
  61. {
  62.   scanf("%d",&l1);
  63.   for(i=0;i<l1;i++) {
  64.     scanf("%d",&A[i]);
  65.   }
  66.   int t;
  67.   scanf("%d",&t);
  68.   while(t--) {
  69.     scanf("%d",&l2);
  70.     for(i=0;i<l2;i++) {
  71.       scanf("%d",&B[i]);
  72.     }
  73.     if(l2==0){
  74.       printf("0\n");
  75.     }
  76.     else {
  77.       lcs();
  78.       memset(B,0,sizeof(B)); 
  79.     } 
  80.   }
  81.   return 0;
  82. }
Success #stdin #stdout 0.02s 62112KB
comments (?)
stdin
copy 
10

5 1 4 3 2 6 5 5 0 7

5

1 5

1 10

4 5 0 4 7

5 4 1 2 3 5

5 2 6 5 0 7
stdout
copy 
1 5 
0
3 5 0 7 
3 1 2 5 
5 2 6 5 0 7
https://ideone.com/lpDppo
language:
C++14 (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!