根据左右孩子是否相同，来判断是否分叉;

#include<bits/stdc++.h>
using namespace std;
const int N=1e5;
string s;
int ne[N];
long long fi;
void dfs(string a,string b)
{
    int len=a.length( );
    int mark=0;
    if(len>1)
    {
        if(a[1]==b[len-2])
        {
        string h1(a,1,len-1),h2(b,0,len-1);
        s+='{';
        mark=s.length( )-1;
        s+=a[0];
        dfs(h1,h2);
        s+='}';
        ne[mark]=s.length( );
        mark=s.length()-1;
        s+='{';
        dfs(h1,h2);
        s+=a[0];
        s+='}';
        ne[s.length()-1]=s.length( );
        ne[mark]=s.length();
         }
        else
        {
       int i;
        for( i=0;i<len-2;i++)
        {
            if(a[1]==b[i])
            {
            break;
            }
        }
        int ll=i+1;
        int lr=len-1-ll;
        if(ll)
        {
        string part1(a,1,ll),part2(b,0,ll-1);
        dfs(part1,part2);
        }
        s+=a[0];
        if(lr)
        {
        string part3(a,ll+1,lr),part4(b,ll,lr-1);
        dfs(part3,part4);
        }
        }
    }
    else
    s+=a[0];
}
void print(string a,int pos)
{
    char t=s[pos];
if(pos>=fi)
    {
    cout<<a<<endl;
    }
 else if(t=='{')
{
    if(ne[pos]==-1)
        print(a,pos+1);
        else
        {
        print(a,pos+1);
        print(a,ne[pos]);
        }
}
else if(t=='}')
    print(a,ne[pos]);
    else
    {
    a+=s[pos];
    print(a,pos+1);
    }
}
int main( )
{

 string a,b;
 cin>>a>>b;
 memset(ne,-1,sizeof ne);
 dfs(a,b);
 fi=s.length( );
 print("",0);
 return 0;
}