목걸이에서 가장 짧게 끊어 내기
구슬 n개를 둥글게 꿴 목걸이가 있다. 구슬마다 영어 소문자 하나가 새겨져 있고, 목걸이 문자열 S의 i번째 글자가 i번째 구슬이다. 둥근 목걸이라 n번째 구슬 다음에는 다시 1번째 구슬이 온다. 목걸이에서 이어진 구슬 몇 개를 끊어 내어, 문자열 T에 있는 글자를 T에 나온 개수 이상씩 모두 가지려 한다. 끊어 내는 구슬은 어떤 구슬에서 시작해 번호가 커지는 쪽(n번째 다음은 1번째)으로 이어진 구슬들이며, 같은 구슬을 두 번 쓸 수는 없다. 끊어 내는 구슬의 수가 가장 적게 하라. 그런 방법이 여럿이면 시작하는 구슬의 번호가 가장 작은 것을 고른다. 시작하는 구슬의 번호와 끊어 내는 구슬의 수를 빈칸으로 나눠 한 줄에 출력하라. 어떻게 끊어도 안 되면 -1을 출력한다.
- 입력
- 첫 줄에 S, 둘째 줄에 T가 주어진다.
둘 다 영어 소문자로만 된 문자열이다.
1 ≤ S의 길이 n ≤ 100,000, 1 ≤ T의 길이 ≤ 100,000 - 출력
- 시작하는 구슬의 번호와 구슬의 수를 빈칸으로 나눠 한 줄에, 또는 -1
cabbad dc
6 2
ab aa
-1