estring.cpp

// by tmt514
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <string>
#include <vector>
#include <unordered_map>
#define SZ(x) ((int)(x).size())
#define FOR(it, c) for(__typeof((c).begin()) it = (c).begin(); it != (c).end(); ++it)
using namespace std;
typedef long long LL;

const int MAXLEN = 13005;
char A[MAXLEN], B[MAXLEN];
int la[MAXLEN][26], lb[MAXLEN][26];
int idA[MAXLEN], idB[MAXLEN];
int base[27]={};
int countsB[27]={};

int dp[500*501*26];
int n;

inline int encode(int x, int y) {
  int ch = A[x+1]-'a';
  return base[ch] + idA[x+1] * countsB[ch] + idB[y+1];
}

void makebase() {
  int cA[26]={};
  for(int i=1;i<=n;i++)
    idB[i] = countsB[B[i]-'a']++;
  for(int i=1;i<=n;i++)
    idA[i] = cA[A[i]-'a']++;
  idA[n+1] = idB[n+1] = 0;
  int b[27]={};
  for(int i=0;i<26;i++)
    b[i] = cA[i] * countsB[i];
  b[26] = 1;
  for(int i=25;i>=0;i--)
    base[i] = base[i+1] + b[i+1];
}

void makelast(char p[MAXLEN], int last[MAXLEN][26]) {
  int v[26]={};
  for(int i=1;i<=n;i++) {
    v[p[i]-'a'] = i;
    for(int j=0;j<26;j++) last[i][j] = v[j];
  }
}

int go(int x, int y) {
  if (x == 0) return MAXLEN;
  int h = encode(x, y);
  if (dp[h]) return dp[h];
  int &res = dp[h];
  for (int i = 0; i < 26; i++) {
    if(la[x][i] > 0 && lb[y][i] == 0) {
      return (res=1);
    }
  }
  int ret = MAXLEN;
  for (int i = 0; i < 26; i++)
    if(la[x][i] > 0)
      ret = min(ret, 1+go(la[x][i]-1, lb[y][i]-1));
  return (res=ret);
}

string output = "";
void trace(int x, int y, int ans) {
  if (x == 0) return;
  for (int i = 0; i < 26; i++) {
    if(la[x][i] > 0 && lb[y][i] == 0) {
      output += (char)(i+'a');
      return;
    }
  }
  for (int i = 0; i < 26; i++)
    if (la[x][i] > 0 && dp[encode(la[x][i]-1, lb[y][i]-1)] == ans-1) {
      trace(la[x][i]-1, lb[y][i]-1, ans-1);
      output += (char)(i+'a');
      return;
    }
  fprintf(stderr, "error!\n");
  return;
}

int main(void) {
  scanf("%s%s", A+1, B+1);
  n = strlen(A+1);
  makelast(A, la);
  makelast(B, lb);
  A[n+1] = 'z'+1;
  makebase();


  int ans = go(n, n);
  printf("%d\n", ans);
  trace(n, n, ans);
  puts(output.c_str());
  return 0;
}