fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. string a, b;
  5. vector<array<int,10>> nextA, nextB;
  6. vector<vector<int>> memoLen;
  7.  
  8. // build next-pos arrays
  9. vector<array<int,10>> buildNext(const string &s) {
  10.     int n = s.size();
  11.     vector<array<int,10>> nxt(n+1);
  12.     for (int d = 0; d < 10; ++d) nxt[n][d] = -1;
  13.     for (int i = n-1; i >= 0; --i) {
  14.         nxt[i] = nxt[i+1];
  15.         nxt[i][s[i]-'0'] = i;
  16.     }
  17.     return nxt;
  18. }
  19.  
  20. // memoized length of best subsequence from (i,j)
  21. int lcsLen(int i, int j) {
  22.     if (i >= (int)a.size() || j >= (int)b.size()) return 0;
  23.     int &res = memoLen[i][j];
  24.     if (res != -1) return res;
  25.     res = 0;
  26.     for (int d = 0; d <= 9; ++d) {
  27.         int ni = nextA[i][d];
  28.         int nj = nextB[j][d];
  29.         if (ni != -1 && nj != -1) {
  30.             res = max(res, 1 + lcsLen(ni+1, nj+1));
  31.         }
  32.     }
  33.     return res;
  34. }
  35.  
  36. // build lexicographically largest string of length = lcsLen(i,j)
  37. string buildSuffix(int i, int j) {
  38.     if (i >= (int)a.size() || j >= (int)b.size()) return "";
  39.     int need = lcsLen(i, j);
  40.     if (need == 0) return "";
  41.     for (int d = 9; d >= 0; --d) {
  42.         int ni = nextA[i][d];
  43.         int nj = nextB[j][d];
  44.         if (ni != -1 && nj != -1) {
  45.             if (1 + lcsLen(ni+1, nj+1) == need) {
  46.                 return string(1, char('0'+d)) + buildSuffix(ni+1, nj+1);
  47.             }
  48.         }
  49.     }
  50.     return "";
  51. }
  52.  
  53. int main() {
  54.     ios::sync_with_stdio(false);
  55.     cin.tie(nullptr);
  56.     if (!(cin >> a >> b)) return 0;
  57.  
  58.     nextA = buildNext(a);
  59.     nextB = buildNext(b);
  60.     memoLen.assign(a.size()+1, vector<int>(b.size()+1, -1));
  61.  
  62.     // fill memo lazily via calls below
  63.     // Now choose best starting non-zero digit to maximize numeric value
  64.     string best = "";
  65.     int bestLen = -1; // length of trimmed result (digits after first non-zero, including it)
  66.  
  67.     for (int d = 9; d >= 1; --d) {
  68.         int ni = nextA[0][d];
  69.         int nj = nextB[0][d];
  70.         if (ni != -1 && nj != -1) {
  71.             int len = 1 + lcsLen(ni+1, nj+1); // trimmed length if start with d
  72.             string cand = string(1, char('0'+d)) + buildSuffix(ni+1, nj+1);
  73.             if (len > bestLen || (len == bestLen && cand > best)) {
  74.                 bestLen = len;
  75.                 best = move(cand);
  76.             }
  77.         }
  78.     }
  79.  
  80.     if (bestLen == -1) {
  81.         // no non-zero start possible; check if we can output "0"
  82.         if (nextA[0][0] != -1 && nextB[0][0] != -1) {
  83.             cout << "0\n";
  84.         } else {
  85.             // no common subsequence at all
  86.             cout << "0\n"; // hoặc "" tùy spec; ở đây in 0 cho an toàn
  87.         }
  88.     } else {
  89.         cout << best << "\n";
  90.     }
  91.     return 0;
  92. }
  93.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
19834
189341
stdout
copy 
1934
https://ideone.com/kobv9l
language:
C++14 (clang 8.0)
created:
4 hours 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!