Informatica Online Judge

  트리의 순회 [1162 / 048A]

Time Limit(Test case) : 1000(ms)
Number of users who solved : 225   Total Tried : 803


The Champion of this Problem (C++) : gs15039 - ms / 208byte
My Best Submission (C++) : N/A

[USACO(Russ cox)]

Background

농부 존은 컴퓨터과학 시간에 이진 트리의 순회 3가지를 배웠다.

첫 번째는 전위우선순회(pre-order traverse)이다.

이 방법은 먼저 루트를 방문하고 왼쪽 서브트리를 전위로, 오른쪽 서브트리를 전위로 탐색한다.

다음으로 중위우선순회(in-order traverse)이다.

이 방법은 먼저 왼쪽 서브트리를 중위로 탐색한 후 루트를 방문하고 오른쪽 서브트리를 중위로 탐색한다.

마지막으로 후위우선순회(post-order traverse)이다.

이 방법은 먼저 왼쪽 서브트리를 후위로, 오른쪽 서브트리를 후위로 탐색한 후 마지막으로 루트를 방문한다.

이 문제에서는 중위우선순회의 결과와 전위우선순회의 결과를 입력받아서 후위우선순회의 결과를 구하는 것이다.

Input

첫 번째 줄에 중위우선순회의 결과가 문자열로 입력된다.
두 번째 줄에 전위우선순회의 결과가 문자열로 입력된다.

각 순회에 대해서 입력되는 문자는 모두 다르며, 알파벳 대문자, 소문자로 구성된다. 즉 최대 길이는 52를 넘지 않는다.

Output

만약 입력된 결과로 후위우선순회가 하나로 결정되면 그 값을 출력하고, 만약 2개 이상의 결과가 존재하면 "-1"을 출력한다.

IO Example

입력
AaEDFCHG
CaADEFGH

출력
AEFDaHGC

* 설명: 다음과 같은 트리일 경우 입 출력 결과를 만족하며 유일하다.

C
/ |
/ |
a G
/ | /
A D H
/ |
E F


Submit : [C/C++] | [C++11] | [Obj-C] | [Java] | [Python]
Prob Analysis : [Problem Statistics] | [Solution]