代码:
#include<iostream>
using namespace std;
int n;
char a[55],b[55];
int dfs(int l,int r,int x,int y){
// printf("**l=%d,r=%d,x=%d,y=%d\n",l,r,x,y);if(l>r) return 0;
// if(l==r) return 1;int i;for(i=x;i<=y;i++){if(a[l]==b[i]) break;}int ld=dfs(l+1,l+i-x,x,i-1)+1;int rd=dfs(l+i-x+1,r,i+1,y)+1;return max(ld,rd);
}
int main(){cin>>n;scanf("%s%s",a,b);printf("%d",dfs(0,n-1,0,n-1));return 0;
}
建树求前序遍历:
#include<iostream>
using namespace std;
int n;
char a[55],b[55];
int ls[55],rs[55];
void dfs(int l,int r,int x,int y,int num){//printf("**l=%d,r=%d,x=%d,y=%d\n",l,r,x,y);int i;for(i=x;i<=y;i++){if(a[l]==b[i]) break;}if(i-x>0){ls[num]=l+1+1; dfs(l+1,l+i-x,x,i-1,ls[num]);}if(y-i>0){rs[num]=l+i-x+1+1;dfs(l+i-x+1,r,i+1,y,rs[num]); }
}
void prit(int num){if(ls[num]) prit(ls[num]);if(rs[num]) prit(rs[num]);printf("%c",a[num-1]);
}
int main(){cin>>n;scanf("%s%s",a,b);dfs(0,n-1,0,n-1,1);prit(1);return 0;
}