가장 긴 공통 괄호 문자열

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

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

S(A, B)에 원소가 하나 이상 있는지 판별하고, 원소가 있다면

S(A, B)에서 가장 길이가 긴 문자열의 길이를 구하는 프로그램을 작성하라.

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

참고

올바른 괄호열의 정의

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

• 한 쌍의 괄호로만 이루어진 문자열 ()는 올바른 괄호열이다.

• X가 올바른 괄호열이면, X를 괄호로 감싼 (X)도 올바른 괄호열이다.

• X와 Y 가 올바른 괄호열이면, X와 Y 를 이어 붙인 XY 도 올바른 괄호열이다.

• 모든 올바른 괄호열은 위 세 가지 규칙을 통해서만 만들어진다.

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

부분문자열의 정의

길이가 l인 문자열 s와 1 ≤ i ≤ j ≤ l인 두 정수 i와 j에 대해, s[i..j]는 s의 i번째 문자에서부터 j번째

문자까지를 모두 순서대로 포함하는 문자열이며, 이러한 문자열들을 문자열 s의 부분문자열이라고 한다.

예를 들어 s가 ()(()()이라면, s[3..5]는 (()이고, s[4..7]은 ()()이다. 따라서 (()과 ()()은 문자열

()(()()의 부분문자열이다. 하지만 )()(은 문자열 ()(()()의 부분문자열이 아니다.

제약 조건

∑|A|는 하나의 입력에서 주어지는 모든 A들의 길이 합,

∑|B|는 하나의 입력에서 주어지는 모든 B들의 길이 합으로 정의한다.

• 1 ≤ T ≤ 500 000

• A와 B는 각각 여는 괄호와 닫는 괄호로만 이루어진 길이가 1 이상인 문자열이다.

• ∑|A| ≤ 500 000

• ∑|B| ≤ 500 000

부분문제

1. (5점) ∑|A| ≤ 100, ∑|B| ≤ 100

2. (13점) ∑|A| ≤ 1 000, ∑|B| ≤ 1 000

3. (23점) ∑|A| ≤ 10 000, ∑|B| ≤ 10 000

4. (17점) A = B

5. (42점) 추가 제약 조건 없음.

가장 긴 공통 괄호 문자열 timer 5초 memory 1024MB

가장 긴 공통 괄호 문자열 5초 1024MB