Nhận xét chính:

• Giả sử ~L_1 \geq L_2~ để có thể tạo ra một chuỗi phím thỏa mãn yêu cầu, cần thỏa mãn hai điều kiện:

  • ~S_2~ là chuỗi con của ~S_1~.

  • ~L_1 - L_2 \geq |S_1| - |S_2|~: Điều này đảm bảo rằng chênh lệch về độ dài tối đa giữa hai ô mật khẩu đủ để xóa đi các ký tự dư thừa trong ~S_1~ mà không vượt quá giới hạn ~L_2~.

• Gọi ~\text{dp}(t_1, t_2, g_1, g_2)~ là số ký tự ít nhất để điền sao cho hiện tại đã khớp được ~t_1~ và ~t_2~ vị trí ở hai xâu ~S_1~ và ~S_2~, cùng như đang thừa giá trị ~g_1~ và ~g_2~ vị trí prefix vào ô 1 và ô 2.

• Chuyển trạng thái như BFS.

• Nhận xét: Chắc chắn ~g_1~ và ~g_2~ không thể dương cùng lúc, như vậy ta chẳng có lợi gì cả. Nên thừa chỉ có một trong hai xâu ~\rightarrow~ giảm state còn ~n^3~.

Nhận xét bổ sung :

Chúng ta giả sử như trước rằng ~L_1 \geq L_2~.

Nhận xét 1 Không bao giờ nên có bất kỳ "rác" nào trong ô thứ nhất. Do đó, chúng ta có thể giả định rằng chúng ta chỉ nhập các chữ cái từ ~S_1~ (hoặc bất kỳ thứ gì nếu ~t_1 = |S_1|~).

Nhận xét 2: Nếu chúng ta nhập một chữ cái mà không đạt đến độ dài tối đa của ~S_2~, thì việc nhập ngay ký tự '\<' sau đó là không cần thiết.

Nhận xét 3: Nếu chúng ta nhập '\<' và có "rác" trong ô thứ hai, thì việc nhập ngay một chữ cái sau đó là không cần thiết.

Nhận xét 4: Nếu không có "rác" trong bất kỳ ô nào, thì chúng ta không nên nhập '\<'.

Chuyển trạng thái: Thật dễ nhận thấy rằng có rất ít tổ hợp phím mà chúng ta thực sự có thể thực hiện. Tất cả các lần nhấn phím sẽ thuộc một trong các dạng sau:

• Đưa chúng ta từ trạng thái ~(t_1, t_2, 0, 0)~ đến trạng thái ~(t_1 + r, t_2, 0, 0)~, trong đó ~r~ là số ký tự được thêm vào từ ~S_1~ mà không ảnh hưởng đến ~S_2~.

• Tổ hợp nhấn phím đưa chúng ta từ trạng thái ~(t_1, t_2, 0, 0)~ đến trạng thái ~(t_1, t_2 + 1, 0, 1)~.

• Thêm một ký tự từ ~S_1~ vào ô thứ nhất và một ký tự từ ~S_2~ vào ô thứ hai.

~\rightarrow~ Giảm trạng thái còn ~\text{dp}(t_1, t_2)~.

#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define trav(a, x) for(auto& a : x)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<tuple<int,int,int>> vt;
typedef vector<vt> vvt;

const int inf = 1e9;
tuple<int,int,int> done = {-1,-1,-1};

int main() {
  freopen("password.inp", "r", stdin);
  freopen("password.out", "w", stdout);

  cin.sync_with_stdio(0); cin.tie(0);
  cin.exceptions(cin.failbit);
  int la, lb;
  string a,b;
  cin >> a >> la >> b >> lb;
  if(la < lb) swap(la,lb), swap(a,b);

  // [index a, index b, active]
  vector<vvi> dp(sz(a)+1, vvi(sz(b)+1, vi(2, inf)));
  vector<vvt> dad(sz(a)+1, vvt(sz(b)+1, vt(2, done)));

  auto move = [&](int i, int j, int q, int ni, int nj, int nq, int cost=0) {
    // try move [i,j,q] -> [ni,nj,nq]
    if(dp[ni][nj][nq] > dp[i][j][q] + cost) {
      dp[ni][nj][nq] = dp[i][j][q] + cost;
      dad[ni][nj][nq] = {i,j,q};
    }
  };

  dp[0][0][0] = 0;
  rep(i,0,sz(a)+1) rep(j,0,sz(b)+1) {
    move(i,j,0, i,j,1);
    if(lb-j <= la-i) move(i,j,1, i,j,0, 2*(lb-j));
    if(i < sz(a) && j < sz(b) && a[i] == b[j]) move(i,j,0, i+1,j+1,0);
    if(i < sz(a)) move(i,j,1, i+1,j,1);
  }

  // reconstruct solution
  int i = sz(a), j = sz(b), q = 0, ni, nj, nq;
  int s = dp[i][j][q];

  if(s == inf) {
    cout << "!";
    return 0;
  }

  vt trans = {{i,j,q}};
  while(trans.back() != done) {
    tie(i,j,q) = trans.back();
    trans.emplace_back(dad[i][j][q]);
  }
  trans.pop_back();
  reverse(all(trans));

  string ans;
  trav(t, trans) {
    tie(ni,nj,nq) = t;
    if(q-nq == 1) ans += string((lb-j), 'q') + string((lb-j), '<');
    if(ni == i+1) ans += a[i];
    tie(i,j,q) = t;
  }
  assert(sz(ans) == s + sz(a));
  cout << (int)ans.size() << '\n' << ans;

  return 0;
}