题目描述

blablabla

样例

#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

struct DLNode{
    char val;
    DLNode *l,*r;
};

string pre,mid;

void last(DLNode *ans){
    if(ans==NULL)return ;

    last(ans->l);
    last(ans->r);
    printf("%c",ans->val);

}

void build(DLNode *ans,int prel,int prer,int midl,int midr,int isleft){
    if(prel>prer)return ;

    char data=pre[prel];
    int location;
    for(int i=midl;i<=midr;i++)
       if(data==mid[i]){
           location=i;
           break;
       }

    int cntl=location-midl,cntr=midr-location;
    DLNode *temp=(DLNode *)malloc(sizeof(DLNode));
    temp->val=data;

    if(isleft==1)ans->l=temp;
    else ans->r=temp;

    build(temp,prel+1,prel+cntl,midl,location-1,1);
    build(temp,prel+cntl+1,prer,location+1,midr,0);



}
int main()
{
    while(getline(cin,pre)){
        getline(cin,mid);
        DLNode *ans=(DLNode *)malloc(sizeof(DLNode));
        build(ans,0,pre.length()-1,0,mid.length()-1,1);
        last(ans->l);
        printf("\n");
    }



    return 0;
}

算法1

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

blablabla