fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. struct LCS {
  5.     struct Vec {
  6.         int W;
  7.         vector<uint64_t> v;
  8.         Vec(): W(0){}
  9.         Vec(int n) {
  10.             reset(n);
  11.         }
  12.         void reset(int n) { W=(n+63)>>6; v.assign(W,0); }
  13.         void clear() { fill(v.begin(), v.end(), 0); }
  14.         void setbit(int i) { v[i>>6] |= (1ull<<(i&63)); }
  15.         static void OR(Vec &o, const Vec &a, const Vec &b) {
  16.             for (int i=0; i<a.W; i++)
  17.                 o.v[i]=a.v[i]|b.v[i];
  18.         }
  19.         static void AND(Vec &o, const Vec &a, const Vec &b) {
  20.             for (int i=0; i<a.W; i++)
  21.                 o.v[i]=a.v[i]&b.v[i];
  22.         }
  23.         static void NOT(Vec &o, const Vec &a) {
  24.             for (int i=0; i<a.W; i++)
  25.                 o.v[i]=~a.v[i];
  26.         }
  27.         static void SHL1(Vec &o, const Vec &a) {
  28.             uint64_t c=0;
  29.             for (int i=0; i<a.W; i++) {
  30.                 uint64_t nv=a.v[i]<<1|c;
  31.                 c=a.v[i]>>63;
  32.                 o.v[i]=nv;
  33.             }
  34.         }
  35.         static void SUB(Vec& o, const Vec& a, const Vec& b) {
  36.             uint64_t bor=0;
  37.             for(int i=0; i<a.W; i++) {
  38.                 unsigned __int128 bi=(unsigned __int128)b.v[i]+bor;
  39.                 unsigned __int128 ai=a.v[i];
  40.                 o.v[i]=(uint64_t)(ai-bi);
  41.                 bor=ai<bi;
  42.             }
  43.         }
  44.         int popcnt() const {
  45.             int s=0;
  46.             for(auto x: v)
  47.                 s+=__builtin_popcountll(x);
  48.             return s;
  49.         }
  50.     };
  51.  
  52.     // --- prefix LCS lengths: L[j] = LCS(A[as..ae], B[bs..bs+j-1]) ---
  53.     static vector<int> pref(string &A, int as, int ae, string &B, int bs, int be) {
  54.         int n=ae-as+1, m=be-bs+1;
  55.         array<Vec, 256> M;
  56.         for (int c=0; c<256; c++) M[c]=Vec(n);
  57.         for (int i=0; i<n; i++) M[(unsigned char)A[as+i]].setbit(i);
  58.         Vec S(n), X(n), Y(n), T(n), NX(n);
  59.         S.clear();
  60.         vector<int> L(m+1, 0);
  61.         for (int j=0; j<m; j++) {
  62.             unsigned char ch=(unsigned char)B[bs+j];
  63.             Vec::OR(X, M[ch], S);
  64.             Vec::SHL1(Y, S);
  65.             if (Y.W) Y.v[0]|=1ULL;
  66.             Vec::SUB(T, X, Y);
  67.             Vec::NOT(NX, T);
  68.             Vec::AND(S, X, NX);
  69.             L[j+1]=S.popcnt();
  70.         }
  71.         return L;
  72.     }
  73.     // --- suffix LCS lengths: R[k] = LCS(A[mid+1..ae], B[bs+k..be]) ---
  74.     static vector<int> suff(string &A, int as, int ae, string &B, int bs, int be) {
  75.         string Ar, Br;
  76.         Ar.reserve(ae-as+1);
  77.         Br.reserve(be-bs+1);
  78.         for (int i=ae; i>=as; i--) Ar.push_back(A[i]);
  79.         for (int j=be; j>=bs; j--) Br.push_back(B[j]);
  80.         return pref(Ar, 0, (int)Ar.size()-1, Br, 0, (int)Br.size()-1);
  81.     }
  82.  
  83.     static string lcs(string &a, string &b, int as, int ae, int bs, int be) {
  84.         if (as>ae || bs>be) return "";
  85.         if (as==ae) {
  86.             for (int j=bs; j<=be; j++) if (a[as]==b[j])
  87.                 return string(1, a[as]);
  88.             return "";
  89.         }
  90.         int amid=(as+ae)/2;
  91.         auto L1=pref(a, as, amid, b, bs, be);
  92.         auto L2=suff(a, amid+1, ae, b, bs, be);
  93.         int best=-1, bj=0;
  94.         for (int j=0; j<=be-bs+1; j++) {
  95.             int c=L1[j]+L2[be-bs+1-j];
  96.             if (c>best)
  97.                 best=c, bj=j;
  98.         }
  99.         string l=lcs(a, b, as, amid, bs, bs+bj-1);
  100.         string r=lcs(a, b, amid+1, ae, bs+bj, be);
  101.         return l+r;
  102.     }
  103.     // --- open API ---
  104.     static pair<int, string> run(string& a, string& b) {
  105.         if (a.empty() || b.empty())
  106.             return {0,""};
  107.         string s=lcs(a, b, 0, a.size()-1, 0, b.size()-1);
  108.         return {s.size(), s};
  109.     }
  110. };
  111.  
  112. int main() {
  113.     cin.tie(0)->sync_with_stdio(0);
  114.     string a, b;
  115.     cin >> a >> b;
  116.     auto [len, s]=LCS::run(a, b);
  117.     cout << len << '\n' << s;
  118. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
ACAYKP
CAPCAK
stdout
copy 
4
ACAK
https://ideone.com/N8AnR0
language:
C++ (gcc 8.3)
created:
10 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!