O(n)!!!

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

unordered_map<char, int> in_index;

void build(int preL, int preR, int inL, int inR, const string& preorder, const string& inorder) {
    if (preL > preR) return;

    char root = preorder[preL];
    int pos = in_index[root];  // O(1) 查找
    int left_cnt = pos - inL;

    // 递归左子树
    build(preL + 1, preL + left_cnt, inL, pos - 1, preorder, inorder);
    // 递归右子树
    build(preL + left_cnt + 1, preR, pos + 1, inR, preorder, inorder);

    cout << root;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    string preorder, inorder;
    cin >> preorder >> inorder;

    // 预处理：记录中序中每个字符的位置
    for (int i = 0; i < inorder.size(); ++i) {
        in_index[inorder[i]] = i;
    }

    build(0, preorder.size()-1, 0, inorder.size()-1, preorder, inorder);
    cout << endl;

    return 0;
}