문자열 비교
문제 정보
-
- 문제 ID
- 시간 제한
- 메모리 제한
- 제출 횟수
- 정답 횟수 (비율)
-
- 출처
- 분류
문제
ACM(Ap Chook Method)형식으로 압축된 두 문자열 A, B가 주어진다. 압축을 풀었을 때, 두 문자열이 같은지 비교하는 프로그램을 작성하시오.
ACM 형식 압축
- ACM 형식 압축은 알파벳 대문자로 구성된 문자열을 압축한다.
- 괄호와 숫자를 이용해 반복되는 부분 문자열을 짧게 표현할 수 있다. 예를 들어, RUNRUNRUN을 (RUN)^3으로 표현할 수 있다.
- 괄호 안에는 적어도 하나 이상의 알파벳 대문자가 들어가고, 알파벳 대문자 외에 다른 문자는 들어갈 수 없다. 다시 말해, 괄호 안에 다시 괄호가 들어갈 수는 없다.
- ')' 바로 다음에는 항상 '^'를 쓰고, '^' 바로 다음에는 괄호 안의 문자열이 반복되는 횟수를 쓴다.
- 반복되는 횟수는 1이상 1억 이하의 정수다.
아래는 ACM 형식으로 압축된 문자열에 대한 몇 가지 예제다. 왼쪽은 압축된 문자열이고, 오른쪽은 압축을 푼 문자열이다.
C(O)^2KIE(RUN)^5 = COOKIERUNRUNRUNRUNRUN
CO(OKIER)^1(UNR)^4UN = COOKIERUNRUNRUNRUNRUN
KCM(HAD)^2HI(S)^2ECONDWFEARLY = KCMHADHADHISSECONDWFEARLY
KR(I)^3T(O)^2 = KRIIITOO
JONGMANALSO = JONGMANALSO
입력
첫 번째 줄에 테스트 케이스의 수 T가 주어진다.
각 테스트 케이스는 두 줄로 구성되며 첫 번째 줄에는 압축된 문자열 A, 두 번째 줄에는 압축된 문자열 B가 주어진다. 압축된 문자열 A와 B의 길이는 5이상 1000이하이고, 압축을 푼 문자열은 알파벳 대문자로만 구성된다. 위에 설명한 형식에 어긋나는 입력은 주어지지 않는다.
출력
각 테스트 케이스에 대해 압축을 풀었을 때, 두 문자열이 같으면 "YES"를 출력하고, 다르면 "NO"를 출력한다.
예제 입력
3 C(O)^2KIE(RUN)^5 COOKIER(UNR)^4UN C(O)^2KIE(RUN)^50 CO(OKIER)^1(UNR)^49UN KR(I)^3(I)^4 K(RI)^4
예제 출력
YES YES NO
노트
