toj~3988~귀속 두 갈래 나무 세 가지 반복의 전환

2256 단어
3988.   
Password
Time Limit: 1.0 Seconds   
Memory Limit: 65536K
Total Runs: 476   
Accepted Runs: 200
Bob will get a bag as gift from Alice, but Alice don't wanna Bob get the bag without did anything, so she put the bag into a safe box... Alice will give two hints about password to Bob. One is the preorder traversal(root, left subtree, right subtree) of a binary tree, another is the inorder traversal(left subtree, root, right subtree) of the same tree. The password is the postorder traversal(left subtree, right subtree, root) of the tree.For example:
The tree only has three nodes A, B and C.
Its preorder traversal is ABC, inorder traversal is BAC, and postorder traversal is BCA.
 

Input


There are several test cases in the input file, Each test case contains two line. Preorder traversal and Inorder traversal.(Each line's length won't longer than 26, and only contain upper letter)

Output


For each test case, output the password Bob need.

Sample Input


 
ABC
BAC

 

Sample Output


 
BCA

 
Source: TJU Team Selection 2013
#include
#include
#include
using namespace std;

char ans[30];  // 
int t=0;

void solve(string s1,string s2)
{

    if(s1.length()==0) return ;
    else if(s1.length()==1)
    {
        ans[t++]=s1[0];
        return ;
    }
    else {
        int tt=s2.find(s1[0]);
        solve(s1.substr(1,tt),s2.substr(0,tt));  // 
        solve(s1.substr(tt+1,s1.length()-tt-1),s2.substr(tt+1,s2.length()-tt-1));   // 
        ans[t++]=s1[0];
    }
}
int main()
{
    string stra,strb;
    while(cin>>stra>>strb)
    {
        int len=stra.length();
        t=0;
        solve(stra,strb);
        ans[len]='\0';
        cout<

length () 함수는string류의 구성원 함수로 이 대상 문자열의 길이를 되돌려줍니다.substr () 함수는string류 구성원 함수이고 함수 되돌려 주는 값은 이 문자열의 하위 문자열이며 원형은substr(intpos,intn)입니다.그 중에서pos는 하위 문자열이 시작될 때의 하표이고 n은 함수가 문자열의 길이를 되돌려주는 것을 나타낸다.
다음으로 전송:https://www.cnblogs.com/hellohacker/p/5822833.html

좋은 웹페이지 즐겨찾기