줄임말

문자열 \(A\)가 문자열 \(B\)의 줄임말이라는 것은 \(B\)의 순서를 바꾸지 않고 0 또는 그 이상 개수의 문자를 지워 \(A\)를 만들 수 있다는 뜻이다. 정의에 의해서 \(B\)는 자기 자신의 줄임말임에 유의하라. 예를 들어, ac, ab, aa, aabc는 aabc의 줄임말이고, d, aaa, ba는 aabc의 줄임말이 아니다.

영문 알파벳 소문자로만 이루어진 두 문자열 \(S\)와 \(T\)가 주어진다. \(T\)를 자연수 \(n\)번 반복해서 이어쓴 문자열을 \(T\) \(n\)이라고 하자. \(S\)가 \(T\) \(n\)의 줄임말이 되는 최소의 \(n\)을 구하라.

예를 들어, \(T\) = ac, \(S\) = caa라고 하면, \(T^{1}\) = \(T\) = ac, \(T^{2}\) = acac, \(T^{3}\) = acacac이고 \(n\) = 3일 때 처음으로 \(S\)가 \(T^{n}\)의 줄임말이 된다.

• \(S\)와 \(T\)는 영문 알파벳 소문자(‘\(a\)’ - ‘\(z\)’)만으로 이루어진 문자열이다.
• \(S\)의 길이는 \(1\) 이상 \(1,000,000\) 이하이다.
• \(T\)의 길이는 \(1\) 이상 \(100,000\) 이하이다.

첫째 줄에 문자열 \(S\)가 주어진다.

둘째 줄에 문자열 \(T\)가 주어진다.

\(S\)가 \(T^{n}\)의 줄임말이 되는 최소의 \(n\)을 출력한다. 단, 어떤 \(n\)에 대해서도 \(T^{n}\)이 \(S\)의 줄임말이 되지 못할 때에는, -1을 출력한다.

riseoj 작성

출처 올림피아드 > 한국정보올림피아드 > KOI 2020 > 2차 대회 > 고등부 1번