RNA

RNA는 몸속에서 중요한 일을 하는 분자다. RNA 분자의 구조는 다음 네 조건을 만족하는 순서쌍 $(S, P)$로 나타낸다.

1. 어떤 양의 정수 $n \le 450$에 대해 $S = s_1 s_2 \dots s_n$이고 $P = p_1 p_2 \dots p_n$이다.
2. $S$의 각 원소 $s_i$는 A, C, G, U 중 하나다.
3. $P$의 각 원소 $p_i$는 별표, 여는 괄호, 닫는 괄호 중 하나다.
4. $P$는 균형 잡힌 괄호열이다. 별표를 모두 지우고 나면 각 여는 괄호는 자기 뒤의 닫는 괄호 하나와 일대일로 짝을 이루고, 각 닫는 괄호는 자기 앞의 여는 괄호 하나와 일대일로 짝을 이룬다는 뜻이다.

아래는 RNA 구조 두 개다. 왼쪽이 $A_1 = (S_1, P_1)$, 오른쪽이 $A_2 = (S_2, P_2)$이다.

ACCCGAACUU   AAUAUCCCGAAU
((**)*(*))   *(**)(**)*()

두 RNA 구조 $A = (S, P)$와 $A' = (S', P')$에 대해 $i \le j$인 정수 $i$, $j$가 있어서 $S' = s_i \dots s_j$이고 $P' = p_i \dots p_j$이면 $A'$를 $A$의 부분구조라고 한다. $A'$도 RNA 구조이므로 $P'$의 괄호 역시 균형이 맞아야 한다. 예를 들어

CCCG
(**)

인 $A_3 = (S_3, P_3)$은 $A_1$의 부분구조다. 반면

ACCCGAACU
((**)*(*)

인 $A_4 = (S_4, P_4)$는 $P_4$의 괄호 균형이 맞지 않아 $A_1$의 부분구조가 아니다.

두 RNA 구조 $X$와 $Y$에 대해 $Z$가 둘 모두의 부분구조이면 $Z$를 $X$와 $Y$의 공통 부분구조라고 한다. 최장 공통 부분구조는 공통 부분구조 가운데 길이가 가장 긴 것이다.

위의 $A_1$과 $A_2$라면 최장 공통 부분구조의 길이는 5이고 다음과 같다.

CCCGA
(**)*

다음은 괄호 균형이 맞지 않아서 $A_1$과 $A_2$의 공통 부분구조가 아니다.

CCCGAA
(**)*(

길이가 450 이하인 RNA 구조 두 개가 주어진다. 최장 공통 부분구조의 길이를 구하라.

입력은 네 줄이다. 첫째 줄은 첫 번째 RNA의 염기 서열 $S$, 둘째 줄은 그 괄호열 $P$다. 셋째 줄은 두 번째 RNA의 염기 서열 $S'$, 넷째 줄은 그 괄호열 $P'$다.

한 RNA에서 염기 서열과 괄호열은 길이가 같고, 그 길이는 1 이상 450 이하다.

최장 공통 부분구조의 길이를 한 줄에 출력한다. 공통 부분구조가 하나도 없으면 0을 출력한다.