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;
}