아직 만들고 있는 페이지입니다.

이 페이지는 아직 만드는 중입니다. 보이는 내용은 바뀔 수 있습니다.

Послание

시간 제한2초메모리 제한1024 MB

요약
문자열 c와 s가 주어질 때, c를 여러 번 이어 붙인 뒤 그 사이사이에 메시지 글자를 끼워 넣어 s를 만들 수 있다면, c가 반복된 최대 횟수를 구한다.
난이도

보통10점 중 7점

유형
문자열, 그리디, 투 포인터, 이분 탐색
정답자
아직 제출이 없습니다

문제

Во время одного из своих путешествий доктор Стрэндж столкнулся с серьезной задачей. Ему необходимо расшифровать послание, зашифрованное в строке ss, которую он получил на электронную почту. Он знает, что послание шифруется следующим образом: некоторая строка cc записывается какое-то количество раз (возможно нулевое), затем между произвольными буквами полученной строки вставляются буквы послания (возможно, вставляется сразу несколько букв) и таким образом получается строка ss.

Доктор Стрэндж догадался, какая строка была взята в качестве строки cc и теперь, чтобы расшифровать послание, ему необходимо определить, какое максимальное количество раз могла быть записана строка cc при шифровании. Помогите ему!

입력

В первой строке входного файла дана строка cc.

Во второй строке входного файла дана строка ss.

Каждая строка может состоять из строчных и заглавных букв латинского алфавита. Длина каждой строки не превышает 10610^6 символов.

출력

Выведите единственное число --- ответ на задачу.

예제1

  1. 예제 1

    입력
    ab
abacabaaacbb
    예상 출력
    3