QUDOJ-78 두 갈래 트리 재구성(중간 순서 후속 순서)

Problem 78: 두 갈래 나무 재구성

Time Limit:1 Ms| 
Memory Limit:100 MB
Difficulty:0

Description

제목은 간단합니다. 두 갈래 나무의 후순과 중순 서열을 구해 드리겠습니다 (So easy!).

Input

100 그룹 미만의 여러 데이터 세트를 입력하여 파일의 끝으로 끝냅니다.
각 그룹의 데이터는 단지 한 줄로 두 개의 문자열을 포함하고 중간에 빈칸으로 구분하여 각각 두 갈래 트리의 뒷순서와 중간 순서를 나타낸다(문자열의 길이는 26보다 작고 입력 데이터는 합법성을 보장한다)

Output

각 그룹의 출력 데이터는 단독으로 한 줄을 차지하고, 출력은 대응하는 선순 서열을 차지한다.

Sample Input

ACBFGED ABCDEFG
CDAB CBAD

Sample Output

DBACEGF
BCAD
생각:
이전에 쓴 앞의 순서와 뒤의 순서;
        http://blog.csdn.net/tbl_123/article/details/13631837
코드:

#include <stdio.h>
#include <string.h>
#define N 30

char a[N], b[N];

void f(int a_s, int a_e, int b_s, int b_e);

int main()
{
	while(scanf(" %s %s", b, a) != EOF){
		int len = strlen(a);
		f(0, len - 1, 0, len - 1);
		printf("
");
	}

	return 0;
}

void f(int a_s, int a_e, int b_s, int b_e)
{
	if(a_s == a_e){
		printf("%c", a[a_s]);
		return;
	}
	if(a_s > a_e || b_s > b_e)
		return;
	printf("%c", b[b_e]);
	for(int i = a_s; i <= a_e; i ++){
		if(a[i] == b[b_e]){
			f(a_s, i - 1, b_s, b_s + (i - 1 - a_s));
			f(i + 1, a_e, b_e - 1 - (a_e - (i + 1)), b_e - 1);
		}
	}
}