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

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

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

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

Hint.

올바른 괄호열의 정의

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

• 한 쌍의 괄호로만 이루어진 문자열 ()는 올바른 괄호열이다.
• X가 올바른 괄호열이면, X를 괄호로 감싼 (X)도 올바른 괄호열이다.
• X와 Y 가 올바른 괄호열이면, X와 Y 를 이어 붙인 XY도 올바른 괄호열이다.
• 모든 올바른 괄호열은 위 세 가지 규칙을 통해서만 만들어진다.

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

부분문자열의 정의

길이가 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]은 ()()이다. 따라서 (()과 ()()은 문자열 ()(()()의 부분문자열이다. 하지만 )()(은 문자열 ()(()()의 부분문자열이 아니다.

\(\sum |A|\)는 하나의 입력에서 주어지는 모든 \(A\)들의 길이 합, \(\sum |B|\)는 하나의 입력에서 주어지는 모든 \(B\)들의 길이 합으로 정의한다.

• \(1 \le T \le 500\,000\)
• \(A\)와 \(B\)는 각각 여는 괄호와 닫는 괄호로만 이루어진 길이가 \(1\) 이상인 문자열이다.
• \(\sum |A| \le 500\,000\)
• \(\sum |B| \le 500\,000\)

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

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

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

• S(A, B)가 공집합이라면 0을 출력한다.
• S(A, B)에 원소가 하나 이상 존재한다면, 그 중 가장 길이가 긴 문자열의 길이를 출력한다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2021 > 2차 대회 > 고등부 3번