树的分界点

题目描述

在研究二叉树的遍历序列时，小明发现：

给定一棵二叉树的中序遍历序列和后序遍历序列，如果能够确定整棵树的最高层节点，就可以用它在中序遍历序列中的位置，将整棵树划分为左子树和右子树。

现在给出一棵二叉树的两种遍历序列：

• 第一行为中序遍历序列；
• 第二行为后序遍历序列。

请你找到这个用于划分左右子树的关键节点，并输出它在两个序列中的位置。

输入格式

输入共两行。

第一行输入一个字符串，表示某棵二叉树的中序遍历序列。

第二行输入一个字符串，表示同一棵二叉树的后序遍历序列。

输出格式

输出两个整数，分别表示该关键节点在：

后序遍历序列中的下标 中序遍历序列中的下标

两个整数之间用一个空格隔开。

下标从 0 开始。

输入样例

DBEAC
DEBCA

输出样例

4 3

样例解释

对于给出的两个遍历序列，能够将中序遍历序列划分为左右子树的关键节点为 A。

在后序遍历序列 DEBCA 中，A 的下标为 4。

在中序遍历序列 DBEAC 中，A 的下标为 3。

因此输出：

4 3

数据范围

设字符串长度为 n。

1 ≤ n ≤ 1000

输入的两个字符串长度相同。

字符串只包含大写英文字母。

保证输入数据对应一棵合法二叉树，且每个节点的字符互不相同。

提示

二叉树的后序遍历顺序为：

左子树 → 右子树 → 当前节点

中序遍历中，某个节点左边的部分属于它的左子树，右边的部分属于它的右子树。