파일 업로드

줄임말

profile
실행 시간 제한메모리 제한
1 초512 MB
📃 해결할 문제

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

영문 알파벳 소문자로만 이루어진 두 문자열 SSTT가 주어진다. TT를 자연수 nn번 반복해서 이어쓴 문자열을 TnT^n이라고 하자. SSTnT^n의 줄임말이 되는 최소의 nn을 구하라.

예를 들어, T=T = ac, S=S = caa라고 하면, T1=T=T^1 = T = ac, T2=T^2 = acac, T3=T^3 = acacac이고 n=3n = 3일 때 처음으로 SSTnT^n의 줄임말이 된다.

 

제한사항

  • SSTT는 영문 알파벳 소문자("a" - "z")만으로 이루어진 문자열이다.
  • SS의 길이는 1 이상 1,000,000 이하이다.
  • TT의 길이는 1 이상 100,000 이하이다.
💻 입력

첫째 줄에 문자열 SS가 주어진다.

둘째 줄에 문자열 TT가 주어진다.

🖨️ 출력

SSTnT^n의 줄임말이 되는 최소의 nn을 출력한다. 단, 어떤 nn에 대해서도 TnT^nSS의 줄임말이 되지 못할 때에는, -1을 출력한다.


💻 예제 입력 1
aaaaa
aaa
🖨️ 예제 출력 1
2
💻 예제 입력 2
aaaaaa
aaa
🖨️ 예제 출력 2
2
💻 예제 입력 3
6
1 5 8 10 3 2
🖨️ 예제 출력 3
1
💻 예제 입력 4
5 2
4 2 1
5 3 1
5 4 2
4 5 2
3 8 2
🖨️ 예제 출력 4
1
💻 예제 입력 5
caa
ac
🖨️ 예제 출력 5
3
💻 예제 입력 6
cab
acca
🖨️ 예제 출력 6
-1

출처: KOI 2020 2차대회