가장 긴 공통 괄호 문자열

시간 제한3초메모리 제한1024 MB

요약

두 괄호 문자열 A와 B가 주어질 때, 둘 다의 부분 문자열이면서 올바른 괄호 문자열인 가장 긴 문자열의 길이를 구합니다. 그런 문자열이 없으면 0을 출력합니다.

문제

(와 )만으로 이루어진 두 문자열 A, B가 주어진다.

A의 부분 문자열이면서 B의 부분 문자열이고, 올바른 괄호열인 서로 다른 문자열들의 집합을 $S(A, B)$ 라고 하자.

$S(A, B)$ 에 원소가 하나 이상 있는지 판별하고, 원소가 있다면 $S(A, B)$ 에서 가장 길이가 긴 문자열의 길이를 구하는 프로그램을 작성하라.

하나의 입력 데이터에서 T개의 테스트 케이스를 해결해야 한다.

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

다음 T개의 각 줄에는, 하나의 테스트 케이스를 구성하는 두 문자열 A와 B가 공백 하나를 사이에 두고 주어진다.

각각의 테스트 케이스마다, 주어진 순서대로 한 개의 줄에 출력한다.

$\sum |A|$ 는 하나의 입력에서 주어지는 모든 A의 길이 합이고, $\sum |B|$ 는 하나의 입력에서 주어지는 모든 B의 길이 합이다.

올바른 괄호열의 정의

올바른 괄호열은 다음과 같이 정의된다.

예를 들어 (()(()))와 (())()()는 올바른 괄호열이지만, (()와 )((()()는 올바른 괄호열이 아니다.

부분 문자열의 정의

길이가 l인 문자열 s와 $1 \le i \le j \le l$ 인 정수 i, j에 대해, s[i..j]는 s의 i번째 문자부터 j번째 문자까지를 순서대로 이은 문자열이다. 이러한 문자열을 s의 부분 문자열이라고 한다.

예를 들어 s가 ()(()()이면 s[1..5]는 (()이고, s[1..7]은 ()()이다. 따라서 (()과 ()()은 ()(()()의 부분 문자열이다. 하지만 )()(은 ()(()()의 부분 문자열이 아니다.

예제 1

입력

3
()((())) (()((())))()
))(()(((( )())))))(
())) )))))(())

예상 출력

8
2
2