fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define DIM 1024
  3. #define FIN "cmlsc.in"
  4. #define FOUT "cmlsc.out"
  5.  
  6. using namespace std;
  7.  
  8. ifstream fin(FIN);
  9. ofstream fout(FOUT);
  10.  
  11.  
  12. void lcs(int *str1, int *str2, int n, int m) {
  13.  
  14.     int table[n+1][m+1];
  15.  
  16.     for(int i = 0; i <= n; ++i) {
  17.  
  18.         for(int j = 0; j <= m; ++j) {
  19.  
  20.             if(i == 0 || j == 0) table[i][j] = 0;
  21.  
  22.             else if(str1[i-1] == str2[j-1]) {
  23.  
  24.                  table[i][j] = 1 + table[i-1][j-1];
  25.  
  26.             } else {
  27.  
  28.                  table[i][j] = max(table[i][j-1], table[i-1][j]);
  29.             }
  30.         }
  31.     }
  32.  
  33.     cout<<table[n][m]<<endl;
  34.  
  35.     int i = n, j = m, index = table[n][m];    
  36.  
  37.     int lcs[index+1];    
  38.  
  39.     while(i > 0 && j > 0) {
  40.  
  41.           if(str1[i-1] == str2[j-1]) {
  42.  
  43.               lcs[index-1] = str1[i-1];
  44.  
  45.               i--;j--;index--;
  46.  
  47.           } else if(table[i-1][j] > table[i][j-1]) {
  48.  
  49.               i--;
  50.           } else {
  51.               j--;
  52.           }
  53.     }
  54.     for(int i = 0; i < table[n][m]; ++i) cout<<lcs[i]<<" ";    
  55.  
  56. }
  57.  
  58. int main() {
  59.     int n,m;
  60.     cin>>n>>m;    
  61.     int arr1[DIM], arr2[DIM];
  62.     for(int i = 0; i < n; ++i) cin>>arr1[i];
  63.     for(int i = 0; i < m; ++i) cin>>arr2[i];
  64.     lcs(arr1,arr2,n,m);
  65. }
Success #stdin #stdout 0.01s 6588KB
comments (?)
stdin
copy 
812 1020
150 152 101 5 10 59 49 25 8 13 69 101 129 141 140 137 101 140 5 37 4 98 142 65 17 99 85 87 150 21 146 110 150 109 38 45 79 101 21 76 85 111 111 81 79 143 87 98 66 128 60 69 125 6 121 53 20 136 89 72 13 150 79 14 38 68 86 101 9 58 80 121 9 21 11 85 40 107 34 115 82 17 51 17 30 90 60 115 95 4 84 148 38 12 119 131 153 104 31 40 127 140 101 42 54 57 101 67 68 26 60 103 134 59 88 18 75 20 9 124 117 17 71 71 22 8 100 108 22 47 89 135 30 102 24 66 136 82 140 78 85 123 119 21 66 89 2 96 25 15 124 4 110 87 19 42 29 18 64 79 125 102 12 139 21 11 108 26 153 113 141 1 104 101 70 52 119 134 140 95 23 142 44 20 93 43 25 58 80 6 114 99 88 153 28 19 51 68 76 122 16 104 4 67 112 76 113 30 139 116 109 139 19 33 1 38 146 63 20 55 60 155 119 85 55 139 51 123 10 105 23 17 25 133 14 5 115 146 11 21 134 123 68 105 57 19 50 134 32 31 114 83 146 11 91 93 129 7 92 50 114 149 19 86 102 78 88 40 139 18 11 49 84 85 106 107 100 16 72 81 59 120 61 11 111 14 91 87 91 33 87 34 91 109 100 54 32 41 139 155 22 152 54 122 136 43 60 54 66 73 90 16 6 111 98 17 75 36 58 77 118 116 137 81 1 69 30 21 154 111 40 56 79 71 103 1 23 119 64 21 84 129 78 113 146 13 101 87 129 141 106 142 109 118 97 140 146 119 68 85 141 127 152 56 151 115 82 124 85 72 18 55 61 2 4 137 126 58 8 13 16 113 113 24 92 79 52 75 76 19 56 108 80 67 96 84 142 108 51 143 52 120 127 39 99 141 80 62 23 4 106 109 22 20 73 141 56 37 49 124 16 60 109 45 65 155 142 79 22 60 86 86 110 66 155 73 92 128 32 16 83 77 135 137 3 87 155 2 59 79 104 84 144 105 18 38 64 29 41 122 140 25 35 102 86 100 135 87 20 45 151 52 143 76 41 61 145 18 133 1 59 38 71 97 113 59 40 38 154 73 61 70 84 139 146 140 153 128 148 81 137 17 32 153 49 123 16 80 36 90 31 144 16 65 144 14 155 150 143 9 92 59 97 34 46 84 86 36 31 30 141 72 129 109 147 23 89 132 129 140 94 146 92 49 103 29 94 65 108 51 80 114 7 83 107 120 54 53 116 64 107 110 36 49 80 64 60 113 137 152 51 98 116 39 95 50 100 111 75 14 139 56 110 155 73 36 60 20 14 132 87 4 56 141 15 45 70 48 65 100 6 126 11 127 29 3 74 37 61 155 21 125 12 93 78 102 90 24 99 108 20 15 103 20 79 139 50 101 13 3 43 139 32 122 50 103 61 31 50 115 72 137 2 147 40 50 104 49 58 150 16 4 90 6 128 16 33 143 51 43 120 96 128 75 11 89 97 121 1 3 148 26 82 49 122 97 104 99 39 12 107 91 93 32 31 130 4 35 117 93 64 120 40 106 49 25 126 137 101 32 120 66 114 13 89 9 10 56 31 5 17 104 31 130 69 140 36 146 6 38 40 65 54 32 59 125 15 6 144 110 37 152 46 150 35 135 35 60 15 30 100 2 80 79 91 17 32 152 69 23 122 154 27 56 8 98 52 103 118 103 77 8 31 92 124 89 127 92 24 65 144 8 108 111 70 94 121 3 110 138 105 9 88 53 41 51 9 17 59 28 128 98 100 54 37 137 77 73 8 4 66 34 57 3 118 143 99 141 145 23 40 125
98 47 14 40 73 74 99 23 155 153 11 40 41 40 46 103 106 131 61 147 42 69 71 24 122 142 84 117 7 18 3 64 130 119 155 124 123 90 28 95 132 6 150 136 141 64 117 121 130 112 65 84 14 127 118 22 152 45 115 20 122 133 150 53 9 107 123 39 119 84 79 149 50 86 50 89 103 37 124 18 13 17 81 145 141 111 116 49 106 11 2 13 2 58 118 22 24 147 41 72 120 68 70 109 93 131 47 132 29 144 63 128 141 117 84 49 153 49 61 61 79 3 125 139 112 97 42 53 37 107 17 27 30 11 90 90 85 4 104 25 150 100 28 6 140 146 46 88 15 66 17 89 58 143 23 139 146 90 116 83 60 149 75 138 138 89 11 50 87 113 133 119 129 33 101 57 54 126 30 116 69 84 39 87 143 147 151 109 83 106 55 81 154 94 56 30 21 48 34 43 151 52 133 90 24 130 16 12 84 2 93 4 1 1 33 14 145 149 57 29 7 100 145 77 123 74 2 38 114 32 153 54 79 59 146 135 105 24 20 11 50 125 51 135 138 13 49 92 31 94 87 110 19 40 106 14 14 99 45 149 34 72 124 155 118 91 36 84 51 120 40 31 138 94 125 88 73 120 98 21 35 57 130 57 125 154 154 51 124 91 75 106 135 129 50 14 126 124 134 58 54 61 10 50 145 3 131 4 81 108 107 52 136 75 18 36 122 48 81 111 5 74 58 8 56 72 20 47 153 73 39 144 50 49 79 150 96 76 44 41 128 15 32 29 125 12 105 54 22 90 49 130 76 50 151 140 63 46 31 58 3 145 52 143 103 131 134 96 153 41 61 95 1 69 9 40 88 124 84 7 84 126 132 135 27 123 107 154 3 58 47 98 118 40 21 64 30 146 129 107 39 58 40 101 51 95 90 43 136 123 21 119 30 32 47 127 95 73 117 25 81 38 11 47 133 102 17 82 105 147 102 21 140 101 29 122 33 125 47 89 11 136 112 110 6 83 47 61 2 11 22 28 143 31 105 129 15 73 93 97 122 118 31 21 95 59 65 42 17 83 55 75 6 110 15 129 107 125 98 116 56 47 119 139 74 128 14 124 122 84 54 89 97 112 141 100 28 67 144 113 129 81 150 138 31 73 123 125 77 153 19 60 100 128 136 10 9 27 108 124 136 64 8 105 148 154 75 81 123 8 119 145 7 41 14 11 138 58 97 27 95 12 53 17 94 88 65 29 53 31 60 26 55 113 59 119 75 105 99 28 94 11 80 144 126 127 115 79 115 57 122 120 88 18 104 130 26 50 34 1 137 82 125 71 23 43 49 9 115 144 102 104 11 142 44 67 49 26 117 59 57 2 62 144 145 2 38 2 111 137 141 35 72 5 125 56 78 84 56 122 13 149 82 42 106 28 48 17 139 11 140 65 100 129 5 46 30 150 85 129 83 10 75 108 42 146 86 138 50 93 53 9 115 27 63 101 33 16 28 63 22 37 72 80 34 26 119 12 123 41 71 140 40 85 58 70 70 35 9 95 83 5 131 17 50 114 27 152 111 2 130 70 103 109 22 4 11 100 61 39 143 125 3 29 39 37 95 93 116 142 41 115 139 107 68 38 44 54 21 153 50 48 109 29 14 120 103 136 62 117 28 117 5 16 16 3 115 50 91 40 38 77 67 95 149 90 92 115 85 38 13 64 5 152 94 21 26 66 145 102 94 40 70 127 75 23 138 9 149 125 76 149 120 133 116 37 17 132 151 90 16 146 79 153 24 68 8 83 29 150 92 127 19 4 84 134 123 53 109 108 76 135 87 153 55 96 143 55 34 38 87 58 127 12 133 38 83 61 119 14 147 30 105 24 147 155 142 21 74 44 1 83 38 142 91 125 117 144 128 1 22 129 80 48 151 134 107 66 24 36 2 93 153 66 101 118 87 1 27 31 51 24 79 51 126 6 47 76 62 129 117 115 152 129 24 50 38 47 52 39 127 72 138 150 11 76 4 123 121 127 11 13 84 91 55 51 50 74 58 60 133 135 63 118 110 8 128 126 143 143 87 123 103 4 58 138 79 131 143 28 77 44 143 149 66 67 94 112 62 120 74 31 110 12 1 147 115 130 145 17 117 97 107 11 5 143 44 18 14 62 123 28 103 115 151 128 119 135 76 63 141 66 16 113 142 43 118 58 88 147 9 71 88 25 128 93 34 77 106 62 152 72 122 95 77 42 130 57 71 57 147 11 66 115 11 103 60 5 91 38 47 44 60 47 137 95 120 8 49 17 62 135 74 90 27 117 24 70 124 148
stdout
copy 
126
98 99 69 6 121 20 150 9 107 119 103 124 17 22 24 29 79 125 139 11 104 25 6 88 139 146 60 119 55 133 14 57 114 146 11 50 19 40 106 14 34 155 73 98 21 154 106 124 61 4 52 75 56 20 73 49 79 128 32 29 151 52 143 41 61 1 40 154 73 61 139 153 128 148 81 123 14 97 94 65 53 60 113 50 111 56 56 48 65 100 108 50 115 72 40 58 4 11 3 39 93 120 40 13 5 40 125 37 150 135 30 80 79 152 52 118 103 77 94 110 17 28 128 66 34 57
https://ideone.com/Cr2Kat
longest common subsequence for Integers
language:
C++ (gcc 8.3)
created:
1 year 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!