Substring Expression
Time limit8sMemory limit512 MB
Count the contiguous substrings whose removal from a valid tree encoding leaves a string that still encodes a valid tree.
- Level
Medium7 of 10
- Topics
- String, Stack, Tree, Combinatorics
- Solved
- No attempts yet
Problem
Trees are sometimes represented in the form of strings. One of the most popular ways to represent unlabeled trees is as follows.
- Leaves are represented by "()".
- Other nodes (that is, internal nodes) are represented by ( S1 S2 ... Sn ), where Si is the string representing the i-th subnode.
For example, the tree depicted in the figure below is represented by the string "((()())())".
A strange boy named Norward plays with such strings. He has found that a string sometimes remains valid as the representation of a tree even after one successive portion is removed from it. For example, removing the underlined portion from the string "((()())())" results in "((()))", which represents the tree depicted below.
However, he has no way to know how many ways of such removal there are. Your task is to write a program for it, so that his curiosity is fulfilled.
Input
The input contains a string that represents some unlabeled tree. The string consists of up to 100,000 characters.
Output
Print the number of portions of the given string such that removing them results in strings that represent other valid trees.