P1944 Longest Bracket-Matching Substring

Given a string consisting of the four brackets `(`, `)`, `[` and `]`, find its longest bracket-matching substring. Specifically, a string is bracket-matching if it satisfies the following conditions: - `()` and `[]` are bracket-matching strings. - If A is a bracket-matching string, then (A) and [A] are bracket-matching strings. - If A and B are both bracket-matching strings, then AB is also a bracket-matching string. For example: `()`、`[]`、`([])`、`()()` are bracket-matching strings, while `][` and `[(])` are not. A substring of string $A$ is a string formed by a consecutive block of characters from $A$. For example, `A`、`B`、`C`、`ABC`、`CAB`、`ABCABC` are all substrings of the string `ABCABC`, while `D`、`BA`、`ACB` are not. The empty string is a substring of any string.

Input consists of one line, a non-empty string composed only of `()[]`.

Output one line: the longest bracket-matching substring. If there are multiple substrings with the same length, output the one that appears earlier in the original string.

### Constraints Let $n$ be the length of the input string. For $20\%$ of the testdata, $n \le {10}^2$. For $50\%$ of the testdata, $n \le {10}^4$. For $100\%$ of the testdata, $n \le {10}^6$. Translated by ChatGPT 5