//【问题描述】 // 已知一个二叉树的中序遍历序列和后序遍历序列,求这棵树的前序遍历序列。 // //【输入形式】 // 一个树的中序遍历序列 该树后序遍历序列,中间用空格分开。输入序列中仅含有小写字母,且没有重复的

//【算法思路】
// 1. 后序遍历的最后一个节点为根节点，可以根据此节点在中序遍历中找到左右子树
// 2. 递归构造左子树和右子树
// 3. 前序遍历的第一个节点即为根节点，递归输出整棵树的前序遍历序列

#include <iostream>
#include <string>
using namespace std;

void get_preorder(string inorder, string postorder, int in_start, int in_end, int post_start, int post_end, string& preorder) {
if (in_start > in_end || post_start > post_end) {
return;
}
char root_value = postorder[post_end];
int root_index = in_start;
while (inorder[root_index] != root_value) {
root_index++;
}
preorder += root_value;
int left_size = root_index - in_start;
get_preorder(inorder, postorder, in_start, root_index-1, post_start, post_start+left_size-1, preorder);
get_preorder(inorder, postorder, root_index+1, in_end, post_start+left_size, post_end-1, preorder);
}

int main() {
string inorder, postorder;
cin >> inorder >> postorder;
string preorder = "";
get_preorder(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1, preorder);
cout << preorder << endl;
return 0;
}