POJ 1240 Pre-Post-erous!

k叉树的前序和后续遍历，问一共有多少种这样的k叉树

这个就是树的同构，组合数就能解决

同样的题目在51nod也有的，我的另一篇博客

POJ 1240 Pre-Post-erous!

We are all familiar with pre-order, in-order and post-order traversals of binary trees. A common problem in data structure classes is to find the pre-order traversal of a binary tree when given the in-order and post-order traversals. Alternatively, you can find the post-order traversal when given the in-order and pre-order. However, in general you cannot determine the in-order traversal of a tree when given its pre-order and post-order traversals. Consider the four binary trees below: 

    a   a   a   a

   /   /        

  b   b       b   b

 /          /     

c       c   c       c

All of these trees have the same pre-order and post-order traversals. This phenomenon is not restricted to binary trees, but holds for general m-ary trees as well. 

Input

Input will consist of multiple problem instances. Each instance will consist of a line of the form 
m s1 s2 
indicating that the trees are m-ary trees, s1 is the pre-order traversal and s2 is the post-order traversal.All traversal strings will consist of lowercase alphabetic characters. For all input instances, 1 <= m <= 20 and the length of s1 and s2 will be between 1 and 26 inclusive. If the length of s1 is k (which is the same as the length of s2, of course), the first k letters of the alphabet will be used in the strings. An input line of 0 will terminate the input. 

Output

For each problem instance, you should output one line containing the number of possible trees which would result in the pre-order and post-order traversals for the instance. All output values will be within the range of a 32-bit signed integer. For each problem instance, you are guaranteed that there is at least one tree with the given pre-order and post-order traversals. 

Sample Input

2 abc cba
2 abc bca
10 abc bca
13 abejkcfghid jkebfghicda
0

Sample Output

4
1
45
207352860

---

看看大佬写的代码终于懂了

#include<stdio.h>
#include<string.h>
char s[27],c[27];
int m,l;
int C(int a,int b)
{
    long long ans=1;
    for(int i=a-b+1; i<=a; i++)ans*=i;
    for(int i=2; i<=b; i++)ans/=i;
    return (int)ans;
}
int f(int l,char* s,char* c)
{
    if(!l)return 1;
    int cur=0,num=0,ans=1;
    while(cur<l)
    {
        for(int i=cur; i<l; i++)
            if(c[i]==s[cur])
            {
                num++;
                ans*=f(i-cur,s+cur+1,c+cur);
                cur=i+1;
                break;
            }
    }
    return ans*=C(m,num);
}
int main()
{
    while(scanf("%d",&m),m)
    {
        scanf("%s%s",s,c);
        int l=strlen(s);
        printf("%d
",f(l-1,s+1,c));
    }
    return 0;
}