USACO American Heritage

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/*
ID: wcr19961
PROG: heritage
LANG: C++11
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

typedef long long LL;
const int maxn = 30;
int L[maxn], R[maxn];
char s1[maxn], s2[maxn];

int Split(int l1, int r1, int l2, int r2) {
if (l1 == r1) {
return 0;
}
char c = s2[l2];
int u = c - 'A' + 1, len = 0;
for (int i = l1; i < r1; ++i) {
if (s1[i] == c) {
break;
}
++len;
}
L[u] = Split(l1, l1 + len, l2 + 1, l2 + len + 1);
R[u] = Split(l1 + len + 1, r1, l2 + len + 1, r2);
return u;
}

void Print(int u) {
if (u == 0) {
return;
}
Print(L[u]);
Print(R[u]);
putchar(u + 'A' - 1);
}

int main() {
freopen("heritage.in", "r", stdin);
freopen("heritage.out", "w", stdout);
scanf("%s%s", s1, s2);
int len = int(strlen(s1));
Print(Split(0, len, 0, len));
puts("");
return 0;
}