P12729 [KOI 2021 Round 2] 最长公共括号子串

试题来源：。中文翻译做了少量本土化修改。 按照[署名—非商业性使用—相同方式共享 4.0 协议国际版](https://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh-hans)进行授权。

给定两个仅由左括号 `(` 和右括号 `)` 组成的字符串 $A$ 和 $B$。 我们定义 $S(A, B)$ 为以下所有字符串的集合： - 是 $A$ 的子串； - 是 $B$ 的子串； - 并且是一个**合法括号序列**； - 集合中元素互不相同。 请你判断 $S(A, B)$ 是否为空集。如果不是，请计算出 $S(A, B)$ 中最长字符串的长度。 你需要解决一个输入中给出的 $T$ 个测试用例。 ### 合法括号序列的定义 合法括号序列的定义如下： - 单独的一对括号 `()` 是合法括号序列； - 若 $X$ 是合法括号序列，则用括号将其包围后的 $(X)$ 也是合法括号序列； - 若 $X$ 和 $Y$ 都是合法括号序列，则其连接后的 $XY$ 也是合法括号序列； - 所有合法括号序列都只能通过以上三种规则构造。 例如：`((()(())))` 和 `(())()()` 是合法括号序列，而 `(()` 和 `)((()()` 都不是合法括号序列。 ### 子串的定义 给定一个长度为 $l$ 的字符串 $s$，以及满足 $1 \leq i \leq j \leq l$ 的两个整数 $i$ 和 $j$，则 $s[i..j]$ 表示从第 $i$ 个字符开始到第 $j$ 个字符为止的连续子串。 例如若 $s = \texttt{()(()()}$，则 $s[3..5] = \texttt{(()}$，$s[4..7] = \texttt{()()}$，因此 `(()` 和 `()()` 都是该字符串的子串。但 `)()(` 不是其子串。

第一行包含一个整数 $T$，表示测试用例数量。 接下来 $T$ 行，每行由两个字符串 $A$ 和 $B$ 组成，中间以一个空格隔开，表示一个测试用例。

对于每个测试用例，按顺序输出一行： - 若 $S(A, B)$ 是空集，输出 $0$ - 否则，输出 $S(A, B)$ 中最长字符串的长度

**约束条件** 设 $\sum |A|$ 表示输入中所有测试用例的字符串 $A$ 的总长度之和，$\sum |B|$ 定义相同。 - $1 \leq T \leq 500\,000$ - 每个字符串 $A$ 和 $B$ 均由 `'('` 和 `')'` 构成，长度均不少于 1 - $\sum |A| \leq 500\,000$ - $\sum |B| \leq 500\,000$ **子任务** 1. （5 分）$\sum |A| \leq 100$，$\sum |B| \leq 100$ 2. （13 分）$\sum |A| \leq 1\,000$，$\sum |B| \leq 1\,000$ 3. （23 分）$\sum |A| \leq 10\,000$，$\sum |B| \leq 10\,000$ 4. （17 分）所有测试用例中均满足 $A = B$ 5. （42 分）无额外约束条件