USACO American Heritage

/*
    ID: m1500293
    LANG: C++
    PROG: heritage
*/


#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;
char mid[50], pre[50];

void dfs(int p1, int p2, int m1, int m2)
{
    if(p1 > p2) return ;
    char root = pre[p1];
    int m_idx;
    for(m_idx=m1; m_idx<=m2; m_idx++) if(mid[m_idx]==root) break;
    int len = m_idx-m1;
    dfs(p1+1, p1+1+len-1, m1, m_idx-1);
    dfs(p1+1+len, p2, m_idx+1, m2);
    printf("%c", root);
}

int main()
{
    freopen("heritage.in", "r", stdin);
    freopen("heritage.out", "w", stdout);
    scanf("%s%s", mid, pre);
    int lenmid = strlen(mid);
    int lenpre = strlen(pre);
    dfs(0, lenpre-1, 0, lenmid-1);
    printf("\n");
    return 0;
}