题解 | #Pre-Post#

#include <iostream>

const int N = 30;

using namespace std;

int n;        // n叉树
int dp[N][N]; // 组合数

void cal()
{
    dp[0][0] = 1;
    for (int i = 1; i < N; i++)
    {
        dp[i][0] = 1;
        for (int j = 1; j < i; j++)
            dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
        dp[i][i] = 1;
    }
}

int solve(string pre, string post)
{
    // 去掉根结点
    pre = pre.substr(1, pre.size() - 1), post = post.substr(0, post.size() - 1);

    // 符合条件的n叉树的个数为sum，根结点的子树数为k
    int sum = 1, k = 0, pre_pos = 0, post_pos = 0;

    // 寻找根结点子树，递归求解其方案数
    while (pre_pos < pre.length() && post_pos < post.length())
        // 结点相同时，pre_pos为子树串起点位置，post_pos为子树串终点点位置
        if (post[post_pos] == pre[pre_pos])
        {
            // 分别从pre和post串中取出起点为pre_pos，长度为post_pos - pre_pos + 1的子串，递归求解
            sum *= solve(pre.substr(pre_pos, post_pos - pre_pos + 1), post.substr(pre_pos, post_pos - pre_pos + 1));
            // 子树个数加1，更新下标
            k++, pre_pos = ++post_pos;
        }
        // 结点不同时，post_pos递增
        else
            ++post_pos;

    // 乘以组合数
    return sum * dp[n][k];
}

int main()
{
    cal();
    string pre, post;
    while (cin >> n >> pre >> post)
        cout << solve(pre, post) << endl;
}