学步园

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

 

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

    输入文件共2行，第一行表示该树的前序遍历结果，第二行表示该树的后序遍历结果。输入的字符集合为{a-z}，长度不超过26。

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

abc

cba

4

DP思想

#include<cstdio>
#include<string>
#include<cstring>
int p[27],q[27],f[27][27];
int main()
{
	char a[27],b[27];
	scanf("%s",a+1);scanf("%s",b+1);
  int lena=strlen(a+1);
	for(int i=1;i<=lena;i++)
	 for(int j=1;j<=lena;j++)
	  if (a[i]==b[j]){
			p[i]=j;q[j]=i;break;
		}
	for(int i=1;i<=lena;i++) f[1][i]=1;
	for(int i=2;i<=lena;i++)
	 for(int j=1;j<=lena-i+1;j++){
		f[i][j]=0;
		if(p[j+1]==p[j]-1)f[i][j]=2*f[i-1][j+1];
			else f[i][j]+=f[q[p[j]-1]-j-1][j+1]*f[p[j]-p[j+1]-1][q[p[j]-1]];
		}
 printf("%d\n",f[lena][1]);
 return 0;
}