我们都很熟悉二叉树的前序、中序、后序遍历，在数据结构中常提出这样的问题：已知一棵二叉树的前序和中序遍历，求它的后序遍历，相应的，已知一棵二叉树的后序遍历和中序遍历序列你也能求出它的前序遍历。然而给定一棵二叉树的前序和后序，你却不能确定其中序遍历序列，考虑如下图中的几棵二叉树：

所有这些二叉树都有着相同的前序遍历和后序遍历，但中序遍历却不相同。

输出文件只包含一个不超过长整型的整数，表示可能的中序遍历序列的总数。

abc
cba

4

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <algorithm>
using namespace std;

int read() {
	int x = 0, f = 1; char c = getchar();
	while(!isdigit(c)){ if(c == ‘-‘) f = -1; c = getchar(); }
	while(isdigit(c)){ x = x * 10 + c - ‘0‘; c = getchar(); }
	return x * f;
}

#define maxn 30
int n, f[maxn][maxn][maxn];
char be[maxn], af[maxn];

int main() {
	scanf("%s%s", be + 1, af + 1);
	n = strlen(be + 1);
	
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(be[i] == af[j]) f[i][i][j] = 1;
	for(int i = 1; i <= n + 1; i++)
		for(int j = 0; j <= n + 1; j++) f[i][i-1][j] = 1;
	for(int len = 2; len <= n; len++)
		for(int l = 1; l <= n; l++) {
			int r = l + len - 1;
			for(int x = 1; x <= n; x++) {
				int y = x + len - 1;
				f[l][r][x] = 0;
				if(be[l] != af[y]) continue;
				for(int k = 0; k < len; k++) {
					f[l][r][x] += f[l+1][l+k][x] * f[l+k+1][r][x+k];
//					printf("to [%d, %d][%d, %d]  and  [%d, %d][%d, %d]\n", l+1, l+k, x, x+k-1, l+k+1, r, x+k, x+r-l-1);
				}
//				printf("[%d, %d] and [%d, %d]: %d\n", l, r, x, y, f[l][r][x]);
			}
		}
	
	printf("%d\n", f[1][n][1]);
	
	return 0;
}