KOI 2차 2020 고1- 줄임말 > 문제은행 : 정보올림피아드&알고리즘




4606 : 줄임말

제한시간
1000 ms   
메모리제한
64 MB   
해결횟수
0 회   
시도횟수
0 회   

문제

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

 

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

 

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

 


제약 조건


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

 


부분문제


  1. (8점) S와 T는 알파벳 ‘a’만으로 이루어져 있다.
  2. (13점) S의 길이와 T의 길이 모두 100 이하이다.
  3. (21점) S의 길이는 10,000 이하, T의 길이는 100 이하이다.
  4. (34점) T의 길이는 1,000 이하이다.
  5. (24점) 추가 제약 조건이 없다.​

입력형식

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

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


출력형식

S가 Tn의 줄임말이 되는 최소의 n을 출력한다. 

단, 어떤 n에 대해서도 Tn이 S의 줄임말이 되지 못할 때에는, -1을 출력한다.​ 


입력 예

caa
ac

출력 예

3

입력 예

cab
acca

출력 예

-1


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP