Flip it and Stick it
시간 제한1초메모리 제한1024 MB
0과 1로 이루어진 문자열 S와 길이 3 이하의 문자열 T가 주어질 때, S에서 T가 사라지도록 부분 문자열을 뒤집는 최소 횟수를 구합니다. 불가능하면 -1을 출력합니다.
문제
Finn은 "Flip it and Stick it"이라는 게임을 하고 있으며, 줄여서 FiSi라고 부른다. FiSi는 0과 1로 이루어진 두 문자열 와 를 가지고 하는 1인용 게임이다. Finn은 다음 형태의 이동을 할 수 있다.
- 의 부분 문자열을 골라 뒤집는다. 조각들은 원래 순서대로 다시 이어 붙여서 새로운 가 된다.
예를 들어 Finn은 101100에서 1부터 세는 인덱스 기준으로 2번째 자리에서 시작하는 부분 문자열 011을 골라, 한 번의 이동으로 111000을 만들 수 있다.
Finn은 가 를 부분 문자열로 포함하지 않으면 이긴다. Finn이 이기기 위한 가장 짧은 이동 순서의 길이를 구하도록 도와라. 이길 수 없다면 그 사실을 알려라.
입력
첫째 줄에 문자열 가 주어진다 (). 둘째 줄에 문자열 가 주어진다 ().
아래 표에서 은 의 첫 번째 비트, 는 두 번째 비트, 은 세 번째 비트를 가리키며, 왼쪽에서 오른쪽으로 읽는다.
출력
필요한 이동 횟수의 최솟값을 출력한다. 이길 수 없으면 -1을 출력한다.