동등한 문자열

면접 대비

시간 제한2초메모리 제한512 MB

요약

길이가 같은 두 문자열을 반으로 나누고 좌우를 바꿀 수 있는 재귀적 동치 관계로 판정한다.

난이도: 보통10점 중 6점
유형: 분할 정복, 문자열, 재귀, 정렬
정답자: 아직 제출이 없습니다

문제

길이가 같은 두 문자열 a, b가 아래 두 조건 중 하나를 만족하면 a와 b는 동등하다(equivalent)고 부른다.

두 문자열이 완전히 같다.
두 문자열의 길이가 짝수이고, a를 길이가 같은 두 조각 a1, a2로 나누고 b를 길이가 같은 두 조각 b1, b2로 나누었을 때 아래 둘 중 하나가 성립한다.
1. a1과 b1이 동등하고, a2와 b2가 동등하다.
2. a1과 b2가 동등하고, a2와 b1이 동등하다.

두 문자열 a, b가 주어지면 두 문자열이 동등한지 판별하라.

입력

첫째 줄에 문자열 a가, 둘째 줄에 문자열 b가 주어진다. 두 문자열의 길이는 서로 같고, 1 이상 200,000 이하이다. 두 문자열은 알파벳 소문자 26개로만 이루어져 있다.

출력

a와 b가 동등하면 YES를, 동등하지 않으면 NO를 출력한다.

힌트

첫 번째 예제에서 a = "aaba"는 a1 = "aa", a2 = "ba"로 나뉘고, b = "abaa"는 b1 = "ab", b2 = "aa"로 나뉜다. a2 = "ba"는 "b"와 "a"로, b1 = "ab"는 "a"와 "b"로 나뉘므로 조건 2의 두 번째 경우에 의해 a2와 b1은 동등하다. a1 = "aa"와 b2 = "aa"는 완전히 같으므로, 다시 조건 2의 두 번째 경우에 의해 a와 b는 동등하다.

두 번째 예제에서 a = "aabb"는 a1 = "aa", a2 = "bb"로 나뉜다. a1과 a2는 각각 한 종류의 글자로만 이루어져 있으므로, a와 동등한 문자열은 "aabb"와 "bbaa" 두 개뿐이다.

예제7

예제 1
입력
```
aaba
abaa
```
예상 출력
```
YES
```
예제 2
입력
```
aabb
abab
```
예상 출력
```
NO
```
예제 3
입력
```
a
a
```
예상 출력
```
YES
```
예제 4
입력
```
a
z
```
예상 출력
```
NO
```
예제 5
입력
```
aabb
bbaa
```
예상 출력
```
YES
```
예제 6
입력
```
abcdef
defabc
```
예상 출력
```
YES
```
예제 7
입력
```
abcdef
abcfed
```
예상 출력
```
NO
```