fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.  
  8.     string a, b;
  9.     cin >> a >> b;
  10.     int n = a.size(), m = b.size();
  11.  
  12.     // Step 1: DP for length
  13.     vector<vector<int>> dp(n+1, vector<int>(m+1, 0));
  14.     for (int i = n-1; i >= 0; i--) {
  15.         for (int j = m-1; j >= 0; j--) {
  16.             if (a[i] == b[j]) dp[i][j] = 1 + dp[i+1][j+1];
  17.             else dp[i][j] = max(dp[i+1][j], dp[i][j+1]);
  18.         }
  19.     }
  20.  
  21.     // Step 2: next occurrence table (0..9)
  22.     const int DIG = 10;
  23.     vector<vector<int>> nextA(n+2, vector<int>(DIG, n));
  24.     vector<vector<int>> nextB(m+2, vector<int>(DIG, m));
  25.     for (int d = 0; d < DIG; d++) {
  26.         nextA[n][d] = nextA[n+1][d] = n;
  27.         nextB[m][d] = nextB[m+1][d] = m;
  28.     }
  29.     for (int i = n-1; i >= 0; i--) {
  30.         nextA[i] = nextA[i+1];
  31.         nextA[i][a[i]-'0'] = i;
  32.     }
  33.     for (int j = m-1; j >= 0; j--) {
  34.         nextB[j] = nextB[j+1];
  35.         nextB[j][b[j]-'0'] = j;
  36.     }
  37.  
  38.     // Step 3: Build lexicographically largest LCS
  39.     string res;
  40.     int i = 0, j = 0, len = dp[0][0];
  41.     while (len > 0) {
  42.         for (int d = 9; d >= 0; d--) { // từ '9' về '0'
  43.             int ni = nextA[i][d];
  44.             int nj = nextB[j][d];
  45.             if (ni < n && nj < m && dp[ni][nj] == len) {
  46.                 res.push_back('0' + d);
  47.                 i = ni + 1;
  48.                 j = nj + 1;
  49.                 len--;
  50.                 break;
  51.             }
  52.         }
  53.     }
  54.  
  55.     cout << res << "\n";
  56. }
  57.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin 
19834
189341
stdout 
1934
https://ideone.com/gGwS42
language:
C++14 (clang 8.0)
created:
25 days 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!