P3719 [AHOI2017 Middle School Division] rexp

To solve various string matching problems, regular expressions are a powerful tool. By defining a system of symbols, regular expressions can describe the properties of the strings to be found. For example, `a|aa` can match `a` or `aa`, and `(a|b)c` can match `ac` or `bc`.

Full regular expressions are too complex. Here, we only consider regular expressions composed of `(`, `)`, `|`, and `a`. The operations follow the rules below: 1. When there are parentheses, we always evaluate the part inside the parentheses first. 2. When two strings (or substrings defined by parentheses) have no symbol between them, we concatenate them as a whole. 3. `|` is the OR operator, meaning you can choose either string on its two sides. If there are multiple OR operators at the same level, it can be viewed as choosing any one of the strings separated by these OR operators. For example, `(aaa)aa|aa|(a(aa)a)`, `(aaaaa)|(aa)|aaaa`, and `aaaaa|aaaa|aa` are equivalent. They all match all-`a` strings of length $2,4$ or $5$. Given a simplified regular expression, write a program to compute the maximum length of an all-`a` string it can match.

One line containing a valid simplified regular expression.

One line containing an integer, which is the maximum length of an all-`a` string that can be matched.

[Constraints] For $20\%$ of the testdata, the expression length does not exceed $100$, and there are no parentheses. For $40\%$ of the testdata, the expression length does not exceed $100$. For $70\%$ of the testdata, the expression length does not exceed $2 \times 10^3$. For $100\%$ of the testdata, the expression length does not exceed $10^5$. The expression is guaranteed to be valid (i.e., the results on both sides of `|` and inside parentheses are non-empty strings). Translated by ChatGPT 5