메시지
면접 대비시간 제한2초메모리 제한1024 MB
문자열 c와 s가 주어질 때, c를 k번 반복한 문자열이 s의 부분 수열이 되는 최대 k를 구합니다.
문제
닥터 스트레인지는 여행 중 어려운 문제에 부딪혔다. 그는 이메일로 받은 문자열 를 해독해야 한다. 메시지는 다음 방식으로 암호화되었다. 문자열 를 몇 번 (0번일 수도 있다) 적는다. 그다음 이렇게 얻은 문자열의 임의의 글자 사이에 메시지의 글자를 끼워 넣는다. 한 번에 여러 글자를 끼워 넣을 수도 있다. 그 결과가 다.
닥터 스트레인지는 이미 암호화에 쓰인 문자열 가 무엇인지 알아냈다. 메시지를 해독하려면 암호화 과정에서 가 적힐 수 있었던 최대 횟수를 구해야 한다.
입력
첫 번째 줄에 문자열 가 주어진다. 두 번째 줄에 문자열 가 주어진다. 각 문자열은 영문 대문자와 소문자로만 이루어진다. 각 문자열의 길이는 을 넘지 않는다.
출력
답을 나타내는 정수 하나를 출력한다.