fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int main() {
  5.     ios::sync_with_stdio(false);
  6.     cin.tie(nullptr);
  7.     string X, Y;
  8.     if (!getline(cin, X)) return 0;
  9.     if (!getline(cin, Y)) return 0;
  10.     int m = (int)X.size(), n = (int)Y.size();
  11.  
  12.     vector<vector<int>> lcs(m + 1, vector<int>(n + 1, 0));
  13.     for (int i = m - 1; i >= 0; --i)
  14.         for (int j = n - 1; j >= 0; --j)
  15.             lcs[i][j] = (X[i] == Y[j]) ? 1 + lcs[i + 1][j + 1] : max(lcs[i + 1][j], lcs[i][j + 1]);
  16.  
  17.     vector<vector<int>> nx(m + 1, vector<int>(26, m)), ny(n + 1, vector<int>(26, n));
  18.     for (int i = m - 1; i >= 0; --i) {
  19.         nx[i] = nx[i + 1];
  20.         nx[i][X[i] - 'a'] = i;
  21.     }
  22.     for (int j = n - 1; j >= 0; --j) {
  23.         ny[j] = ny[j + 1];
  24.         ny[j][Y[j] - 'a'] = j;
  25.     }
  26.  
  27.     string Z;
  28.     int i = 0, j = 0, rem = lcs[0][0];
  29.     while (rem > 0) {
  30.         for (int c = 0; c < 26; ++c) {
  31.             int i1 = nx[i][c], j1 = ny[j][c];
  32.             if (i1 < m && j1 < n && lcs[i1 + 1][j1 + 1] == rem - 1) {
  33.                 Z.push_back(char('a' + c));
  34.                 i = i1 + 1; j = j1 + 1; --rem;
  35.                 break;
  36.             }
  37.         }
  38.     }
  39.  
  40.     vector<vector<int>> scs(m + 1, vector<int>(n + 1, 0));
  41.     for (int i = m - 1; i >= 0; --i) scs[i][n] = m - i;
  42.     for (int j = n - 1; j >= 0; --j) scs[m][j] = n - j;
  43.     for (int i = m - 1; i >= 0; --i)
  44.         for (int j = n - 1; j >= 0; --j)
  45.             scs[i][j] = (X[i] == Y[j]) ? 1 + scs[i + 1][j + 1] : 1 + min(scs[i + 1][j], scs[i][j + 1]);
  46.  
  47.     string Z2;
  48.     i = 0; j = 0;
  49.     while (i < m || j < n) {
  50.         if (i == m) { Z2.push_back(Y[j++]); }
  51.         else if (j == n) { Z2.push_back(X[i++]); }
  52.         else if (X[i] == Y[j]) { Z2.push_back(X[i]); ++i; ++j; }
  53.         else {
  54.             if (scs[i + 1][j] < scs[i][j + 1]) { Z2.push_back(X[i++]); }
  55.             else if (scs[i + 1][j] > scs[i][j + 1]) { Z2.push_back(Y[j++]); }
  56.             else {
  57.                 if (X[i] <= Y[j]) Z2.push_back(X[i++]);
  58.                 else Z2.push_back(Y[j++]);
  59.             }
  60.         }
  61.     }
  62.  
  63.     cout << Z << "\n" << Z2 << "\n";
  64.     return 0;
  65. }
  66.  
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
abcdezf
dexfabc
stdout
copy 
abc
abcdexzfabc
https://ideone.com/Cg8Bvg
language:
C++14 (gcc 8.3)
created:
10 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!