TopCoder

Thumb qz2vnqoblj6vp6q
miku
https://chino.taipei

User's AC Ratio

92.1% (35/38)

Submission's AC Ratio

44.7% (46/103)

Tags

Description

「植物天生地予人穩定心情的力量,不過也得靠個人去追尋,否則縱使有一整排落葉繽紛的樹林圍繞著你,甚至一整座森林,你也容易視而不見。」

──王家祥《遇見一株樹》

從前從前,山腳下住著三兄弟,有一天他們的媽媽對他們說:「孩子們呀,你們都已經長大了。趕快出去住吧~後山上廣大的森林,還等著你們去冒險呢!去吧!」於是三兄弟就這樣啟程了。

走著走著,三兄弟遇到了一個二叉道路,這時候老大玻利歐得對另外兩個人說:「我要在這裡蓋一間茅草屋,定居在此。」於是老大就脫隊了。

老二和老三走著走著,走了好久,看到了一顆樹。老二艾恩歐得說:「我要在這裡蓋一間木頭房子,住在這裡。」於是只有老三坡斯特歐得一個人往深山走去。他選擇了一個大野狼DFS會最後走到的地方,蓋了一間磚屋…

以上這個故事純屬虛構,如有雷同,一定是你看錯了XD。

問題不在這裡,我們現在要介紹一個東西:Binary Tree 的 Traversal(樹的走訪)。

對於每個node,我們先拜訪該node,然後拜訪其左子樹、右子樹,這個方法叫做樹的前序表示法(Pre-order)。
如果我們先拜訪左子樹,然後回到該node並拜訪它,然後再拜訪右子樹,那麼這個方法叫做中序表示法(In-order)。
如果先拜訪左子樹、右子樹,然後才回到該node並拜訪它,那麼這個方法叫做後序表示法(Post-order)。

例如對於這棵樹:


則該樹的三種表示法為:
Pre-order: ABDECF
In-order: DBEACF
Post-order: DEBFCA
<!--給你Pre-order和In-order求Post-order似乎是個可用遞迴解決的題目,但是,我們現在關心的不是這個。-->
注意:問題來囉!

給你一棵樹的Pre-order和In-order,請你求出Post-order。
<!--現在有兩棵樹,給你第一棵樹的Pre-order和第二棵樹的Post-order,請問這兩棵樹有沒有可能長得一樣?如果有可能長得一樣,請輸出可能構成的樹的個數。-->

Input Format

輸入可能包含多筆測試資料,每一筆測試資料包含了兩列,第一列為一個Pre-order,第二列為一個In-order。任何一個order都是由非空白可顯示字元所形成的字串。(即:ASCII碼介於33與127之間者)

你可以假設同一個字串內不會出現兩個以上相同的字元,並且所有字串的長度都小於50個字元。

Output Format

Sample Input


ABDECF
DBEACF

Sample Output


DEBFCA

Hints

Problem Source

原TIOJ1108 / 經典問題練習。Problem Setter: Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 100
No. Time Limit (ms) Memory Limit (KiB)
0 1000 65536