转载请注明本文链接

题目链接：

这个题目的分析预计都被写烂了，我这里就简单的说明一下。事实上认为他们写了好多好多非常浅显的东西，希望我的分析可以给大家减轻点负担。尽管我也是看别人的分析之后才更加理解这个题目。

分析例如以下：

已知前序和后序，

1：我们先知道的，肯定是字符串第一个会等于最后一个

2：既然是m叉树。那么我们就要分析m叉树中有几个还有子树，然后我们就须要分析子树的由来。

3：子树中又有子树。这个就是组合数学中的一件事情分步完毕，则终于的组合为步步相乘。

所以问题的关键就在于我怎么知道子树的存在呢？

找子树的过程，把前一个字符串记为A，后一个记为B

先运行步骤1，即跳过第一个字符，A=A+1。

然后把取出A的第一个字符A[0]。在B中找，直到B[i]==A[0]，就是一个子树

就分析以下最简单的两个吧

2 abc cba    42 abc bca    1

第一个，运行步骤1，剩下bc和cb，找完第一次就发现找完了。所以就仅仅有1个子树，然后再去对bc进行查找

第二个。运行步骤1，剩下bc和bc。找到两个子树

#include 
     
      #include 
      
       int result;int Cal(int n,int m)//计算组合数,从n个中选m个;{	if(m==n)		return 1;	else if (m==1)		return n;	else		return Cal(n-1,m)+Cal(n-1,m-1);}void Count(char *A,char *B,int num){	int n=strlen(A);	if(n==1)		return ;	A=A++;//忽略第一个;	B[n-1]='\0';//忽略最后一个;	int count=0;	while(*A)	{		int i=0;		char newA[27],newB[27];		while(A[0]!=B[i])		{			newA[i]=A[i];			newB[i]=B[i];			i++;		}		newA[i]=A[i];		newB[i]=B[i];		newA[i+1]='\0';		newB[i+1]='\0';		count++;//统计在当前这一层有多少个子树;		A=A+i+1;		B=B+i+1;		Count(newA,newB,num);	}	result=result*Cal(num,count);}int main(){	int n;	char A[27],B[27];	//freopen("data.in","r",stdin);	while(scanf("%d",&n)!=EOF)	{		scanf("%s%s",&A,&B);		result=1;		Count(A,B,n);		printf("%d\n",result);	}}