GOODS - good string
The definition of beauty quotes sequence:
Empty string is a series of beautiful quotes.
If X is a series of beautiful quotes, then [X], (X), {X} is also a beautiful array brackets.
If X, Y ranges are 2 beautiful quotation marks, the sequence XY is also beautiful.
Example: () [() ()] is a row of beautiful quotes. {[)} Is not beautiful array brackets.
Given a string S contains only the brackets. When writing out the characters from position to position i of the string S j (1 <= i <= j <= Length (S)) we obtain the sequence S (i, j). An S (i, j) is good substring of string S if S (i, j) is a series of beautiful quotes. Request the number of good substring of S.
Input
A single line: string S.
The first 10 trials, the length of S is less than 101.
The next 10 trials, the length of S is less than 10001.
10 final test, the length of S is less than 1000001.
Output
A single integer: Number of possible substring of S.
Example
Input: (){](({}))[] Output: 6
Added by: | Phạm Bá Thái |
Date: | 2013-09-06 |
Time limit: | 0.200s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Mine |