https://www.luogu.com.cn/problem/P1030
1 #define bug(x) cout<<#x<<" is "<<x<<endl 2 #define IO std::ios::sync_with_stdio(0) 3 #include <bits/stdc++.h> 4 using namespace std; 5 #define ll long long 6 #define pb push_back 7 const ll mod=1e9+7; 8 const int N=2e5+10; 9 10 char s[N],t[N]; 11 12 struct node{ 13 int c; 14 node *lson,*rson; 15 node(){ 16 lson=NULL; 17 rson=NULL; 18 } 19 }; 20 21 int a[200],b[200],id[200],d[200],n,cnt; 22 23 node *root; 24 25 node* build(node *now){ 26 now =new node(); 27 node *rt,*lt; 28 int k=id[t[cnt]]; 29 d[k]=1; 30 now->c=t[cnt--]; 31 if(k<n&&!d[k+1]){ 32 now->rson=build(now->rson); 33 } 34 if(k>1&&!d[k-1]){ 35 now->lson=build(now->lson); 36 } 37 return now; 38 } 39 40 void preorder(node *now){ 41 printf("%c",now->c); 42 if(now->lson!=NULL)preorder(now->lson); 43 if(now->rson!=NULL)preorder(now->rson); 44 } 45 46 void work(){ 47 preorder(build(root)); 48 } 49 50 int main(){ 51 scanf("%s",s+1); 52 scanf("%s",t+1); 53 cnt=n=strlen(s+1); 54 55 for(int i=1;i<=n;i++){ 56 id[s[i]]=i; 57 } 58 work(); 59 } 60 /* 61 BADC 62 BDCA 63 64 1 2 4 5 3 6 65 4 2 5 1 6 3 66 4 5 2 6 3 1 67 */
贴一个大佬说明链接