문자열 복사

원본 문자열 S의 연속한 일부를 여러 번 복사해 새 문자열 P를 만들려고 한다. 한 번의 연산 copy(s, p)는 S의 s번째 문자부터 연속한 p개의 문자를 가져와, 현재 만들고 있는 문자열의 뒤에 붙인다.

예를 들어 S = "abaabba"이고 목표 문자열이 "aaabbbabbbaaa"라면 copy(3, 2), copy(4, 3), copy(2, 2), copy(5, 2), copy(2, 3), copy(1, 1)을 차례로 수행해 목표 문자열을 만들 수 있다. 중간 문자열은 "aa", "aaabb", "aaabbba"처럼 뒤에 계속 붙으며 길어진다.

문자열 S와 P가 주어질 때, S에서 P를 만들기 위해 필요한 copy 연산의 최소 횟수를 구하시오.

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

두 문자열은 영어 대문자, 영어 소문자, 숫자로만 이루어져 있다. 각 문자열의 길이는 1 이상 1,000 이하이다. 입력은 copy 연산만으로 S에서 P를 만들 수 있는 경우만 주어진다.

P를 만들기 위해 필요한 copy 연산의 최소 횟수를 출력한다.