poj1240

本题为已知M-叉树的前序遍历与后序遍历 要求给出对应树有多少种可能。

与poj2255类似 只要划分出子树 就把问题规模缩小了 然后就可以递归（目前只会写递归）

M叉树的前序遍历为 根      子树1 子树2 ... 子树K（K<=M）

M叉树的后序遍历为 子树1 子树2 ...子树K  根

进一步 根      （根      子树1 子树2 ... 子树K） 子树2 ... 子树K

   （ 子树1 子树2 ... 子树K 根） 子树2 ...子树K  根

可见只要通过前序遍历找出子树1的根就可以从后序遍历找到整个子树1进而将K个子树全部划分出来 （注意递归的方式 找到第一个子树即可开始递归）

代码如下

#include<iostream>
#include<cstring>
#include<stdlib.h>
#include<stdio.h>
using namespace std;
long long c(int m,int k)
{
    long long  sum1=1;
    for(int i=m; i>(m-k); i--)
        sum1=sum1*i;
    for(int i=k; i>1; i--)
        sum1=sum1/i;
    return sum1;
}
char a[28];
char b[30];

long long sum;
/*void sum1(int m,int a1,int a2,int b1,int b2)
{
    if(a1>a2)return;
    int k=1,Jk;
    int Pa[10];
    int Pb[10];
    Pa[1]=a1;
    Pb[0]=b1-1;
    int j=Pb[0];
    for(int i=1;; i++)
    {
        for(Jk=0; b[j]!=a[Pa[i]]; Jk++,j++);
        Pa[i+1]=Pa[i]+Jk;
        Pb[i]=j;
        if(a[Pa[i+1]]=='\0'||Pa[i+1]>a2)break;
        else k++;
    }
    sum=sum*c(m,k);
    for(int i=1; i<=k; i++)
        sum1(m,Pa[i]+1,Pa[i+1]-1,Pb[i-1]+1,Pb[i]-1);
}*/
void sum1(int m,int a1,int a2,int b1,int b2)
{
    if(a1>a2)return;
    int k=1,Jk,tempa1,tempa2,tempb1,tempb2;
    tempa1=a1;
    tempb1=b1-1;
    int j=tempb1;
    for(int i=1;; i++)
    {
        for(Jk=0; b[j]!=a[tempa1]; Jk++,j++);
        tempa2=tempa1+Jk;
        tempb2=j;
        sum1(m,tempa1+1,tempa2-1,tempb1+1,tempb2-1);
        if(a[tempa2]=='\0'||tempa2>a2)break;
        else
        {
            k++;
            tempa1=tempa2;
            tempb1=tempb2;
        }
    }
    sum=sum*c(m,k);
}
int main()
{
    int m,la,lb;
    //freopen("test","r",stdin);
    while(true)
    {
        sum=1;
        b[0]='0';
        cin>>m;
        if(m==0)break;
        cin>>a>>b+1;
        la=strlen(a);
        lb=strlen(b);
        sum1(m,1,la-1,1,lb-2);
        cout<<sum<<endl;
    }
    return 0;
}