AC

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

struct TreeNode {
	char val;
	TreeNode *left;
	TreeNode *right;
	TreeNode(char x) : val(x), left(nullptr), right(nullptr) {}
};


TreeNode *buildTree(const string &mid, const vector<char> &level) {
	if (mid.empty() || level.empty()) {
		return nullptr;
	}
	char rootVal = level[0];
	TreeNode *root = new TreeNode(rootVal);
	size_t rootpos = mid.find(rootVal);

	string lmid = mid.substr(0, rootpos);
	string rmid = mid.substr(rootpos + 1);

	unordered_set<char> lset(lmid.begin(), lmid.end());
	unordered_set<char> rset(rmid.begin(), rmid.end());

	vector<char> lLevel, rLevel;
	for (size_t i = 1; i < level.size(); ++i) {
		if (lset.count(level[i])) {
			lLevel.push_back(level[i]);
		} else if (rset.count(level[i])) {
			rLevel.push_back(level[i]);
		}
	}

	root->left = buildTree(lmid, lLevel);
	root->right = buildTree(rmid, rLevel);

	return root;
}

void firstfind(TreeNode *root) {
	if (root == nullptr) {
		return;
	}
	cout << root->val;
	firstfind(root->left);
	firstfind(root->right);
}

int main() {
	string mid, level;
	cin >> mid >> level;
	vector<char> levelVec(level.begin(), level.end());
	TreeNode *root = buildTree(mid, levelVec);
	string result;
	firstfind(root);
	return 0;
}