Editorial

---

D

summary:

수 $k$를 골라서 s1의 길이 $k$의 prefix, s2의 길이 $k$의 suffix를 서로 swap할 수 있다.

앞의 행위를 여러 번 반복해서 s1과 s2가 같아질수 있는지 여부를 판별하는 문제이다.

solution:

s1을 a, s2를 b라고 하자.

a뒤에 b를 뒤집어 붙인 상태에서 한번 연산을 한다고 생각하면

$ a_0 \dots a_{n-1} b_{n-1} \dots b_0 $인 상태에서 $a_0 \dots a_{k-1}$ 구간과 $b_{n-1} \dots b_{n-1-(k-1)}$ 를 바꾸게 된다.

그러면 $ b_{n-1} \dots b_{n-1-(k-1)} a_k \dots a_n a_0 \dots a_{k-1} b_{n-1-(k-2)} \dots b_0$ 처럼 되게 된다.

이러면 어떤 $a_i$는 b의 $b_{n-1-i}$와 항상 바뀌게 되므로, 둘은 순서가 바뀔 수 있는 하나의 쌍이라고 볼 수 있다.