+/ +x∗-y x∗3z5- 3z 2y αβ We want to report all nodes v in β such that the sub-tree rooted at v is structurally identical to α, ignoring all labels in the nodes. In this case, there are 2 such nodes because: (i) expression α is a sub-expression of β and (ii) sub-expression (5 − (2 − y)) of β has the same tree structure as α. The corresponding sub-trees have been shaded in the syntax tree of β depicted above. Your task is to write an efficient computer program that, given inputs α and β, computes the number of nodes v in β such that the sub-tree rooted at v is structurally identical to α. Input The input consists of several test cases. Each test case consists of two lines: the first line describes the expression α and the second one the expression β. You can assume that 1 ≤ |α| ≤ 400000 and 1 ≤ |β| ≤ 400000, and that these expressions do not contain any blanks.
2/2 Output For each test case, output the number of nodes v in β such that the sub-tree rooted at v is structurally identical to α. Sample Input 1978 ((x+0)+z) (x+(3z)) ((x+(3z))-((5-(2-y))/y)) Sample Output 3 2