34031번 - 하이터치☆메모리

(와 )만으로 이루어진 문자열을 괄호 문자열이라 한다. 그 중에서도 올바른 괄호 문자열은 다음과 같이 정의된다.

1. 빈 문자열은 올바른 괄호 문자열이다.
2. 문자열 $S$가 올바른 괄호 문자열일 때, $S$를 (와 )로 감싼 문자열 $(S)$도 올바른 괄호 문자열이다.
3. 문자열 $S$와 $T$가 올바른 괄호 문자열일 때, 이 두 문자열을 이어붙인 문자열 $S+T$도 올바른 괄호 문자열이다.

올바른 괄호 문자열의 예시로는 ()()(), (()), ()(())()()이 있다.

문자열 $S$의 접두사는 $S$의 첫번째 원소를 포함하는 $S$의 부분 문자열을 의미한다. abcd의 접두사로는 a, ab, abc, abcd가 있다. 빈 문자열은 접두사가 될 수 없음에 유의하라.

두 괄호 문자열 $A$, $B$에 대해, $A$의 길이 $i\,(1\leq i\leq |A|)$의 접두사를 $a_i$, $B$의 길이 $j\,(1\leq j\leq |B|)$의 접두사를 $b_j$라 할 때 $a_i$와 $b_j$를 이어붙인 문자열 $a_i+b_j$가 올바른 괄호 문자열인 순서쌍 $(i,j)$를 하이터치☆메모리라고 한다. 하이터치☆메모리의 개수를 구해보자.

첫째 줄에 괄호 문자열 $A$가 주어진다.

둘째 줄에 괄호 문자열 $B$가 주어진다.

첫째 줄에 하이터치☆메모리의 개수를 출력한다.

• $1\leq |A|\leq 200\, 000$
• $1\leq |B|\leq 200\, 000$

정답이 32비트 정수 범위를 넘을 수 있으므로, C/C++에서는 long long, Java에서는 long과 같은 자료형을 사용하는 것을 권장한다.