문자열 분해기 timer 1s memory 1024MB

어느 날 윤수는 실험실에서 문자열 분해 기법을 개발해냈다. 문자열 분해는 원본 문자열을 아래 과정에 따라 결과 문자열로 만드는 기법이다.

주어진 문자열에서 임의의 부분 문자열을 선택한다.

선택한 부분 문자열을 원본 문자열에서 제거한 후, 문자열이 남아있다면 남은 문자열을 이어 붙인다. 이때, 제거되는 부분 문자열은 버리거나 결과 문자열의 맨 뒤에 연결할 수 있다.

원본 문자열이 남지 않을 때까지 1-2 과정을 반복한다.

문자열 분해기는 문자열이 주어졌을 때 그 문자열에 대해 문자열 분해 기법을 사용한다. 당신은 윤수가 만든 문자열 분해기의 작동 결과가 올바른지 확인해 줄 것을 요청받았다. 원본 문자열 S와 결과 문자열 T가 각각 주어졌을 때, 문자열 S에 문자열 분해를 실행하여 문자열 T를 만들 수 있는지 확인해 보자.