fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <utility>
  4.  
  5. const int MAX_LENGTH = 100;
  6.  
  7. int A[MAX_LENGTH], B[MAX_LENGTH];
  8. int lis[MAX_LENGTH][MAX_LENGTH];
  9. std::pair<int, int> lis_prev[MAX_LENGTH][MAX_LENGTH];
  10.  
  11. void print_longest_common_subsequence(int i, int k) {
  12.     if (i != 0 and k != 0) {
  13.         const auto & pr = lis_prev[i][k];
  14.         print_longest_common_subsequence(pr.first, pr.second);
  15.         if (pr.first == i-1 and pr.second == k-1)
  16.             printf("%d ", A[pr.first]);
  17.     }
  18. }
  19.  
  20. int main() {
  21.     int na, nb;
  22.     while (scanf("%d", &na) == 1) {
  23.         for (int i = 0; i < na; ++i) scanf("%d", A+i);
  24.         scanf("%d", &nb);
  25.         for (int i = 0; i < nb; ++i) scanf("%d", B+i);
  26.         memset(lis, 0, sizeof(lis));
  27.  
  28.         for (int i = 0; i < na; ++i)
  29.             for (int k = 0; k < nb; ++k) {
  30.                 if (A[i] == B[k]) {
  31.                     lis[i+1][k+1] = lis[i][k] + 1;
  32.                     lis_prev[i+1][k+1] = std::make_pair(i, k);
  33.                 } else {
  34.                     if (lis[i+1][k] >= lis[i][k+1]) {
  35.                         lis[i+1][k+1] = lis[i+1][k];
  36.                         lis_prev[i+1][k+1] = std::make_pair(i+1, k);
  37.                     } else {
  38.                         lis[i+1][k+1] = lis[i][k+1];
  39.                         lis_prev[i+1][k+1] = std::make_pair(i, k+1);
  40.                     }
  41.                 }
  42.             }
  43.         printf("lcc length : %d\n", lis[na][nb]);
  44.         print_longest_common_subsequence(na, nb);
  45.         printf("\n");
  46.  
  47.     }
  48.     return 0;
  49. }
Success #stdin #stdout 0s 3580KB
comments (?)
stdin
copy 
8
1 3 2 4 3 5 4 6
4
3 4 5 6
stdout
copy 
lcc length : 4
3 4 5 6
https://ideone.com/KikDRt
language:
C++14 (gcc 8.3)
created:
9 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!