Sub-expression Counting

Suppose we want to search arithmetic expressions for sub-expressions of certain shape. We are consid- ering only fully parenthesized expressions with binary operators, numerical constants, and variables, as defined in the following BNF-like notation: ⟨expr⟩ ::= ⟨var⟩ ::= ⟨num⟩ ::= ⟨digit⟩ ::= ⟨binop⟩ ::= ⟨var⟩ | ⟨num⟩ | (⟨expr⟩⟨binop⟩⟨expr⟩) a|b|···|z ⟨digit⟩ | ⟨digit⟩⟨num⟩ 0|1|···|9 +|-|*|/ For example, consider the arithmetic expressions α and β defined as follows: α : (x+(3∗z)) β : ((x+(3∗z))−((5−(2−y))/y)). The syntax tree associated to each one of these arithmetic expressions is shown below:

+/ +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