Re-verse

면접 대비

시간 제한1초메모리 제한512 MB

요약

0초부터 매초 문자 하나를 외치고 1초부터 N-1초 사이에 다시 시작할 수 있을 때, 주어진 노래를 시작할 수 있는 최대 횟수를 구한다.

문제

시이는 노래를 최대 몇 번 부르기 시작할 수 있는가?

PS를 하며 평화롭게 시간을 보내던 시이는 돌림 노래를 부르기로 하였다. 시이가 부르고자 하는 노래는 영문 대문자 $N$ 개로 이루어진 문자열이다.

시이는 $0$ 초부터 원하는 시각까지 매초 문자 하나를 외친다. 문자를 외치는 시간은 무시할 수 있다. 시이가 $i$ 초부터 $i+N$ 초 직전까지 외친 $N$ 개의 문자들을 이어붙인 문자열이 노래와 일치하면 시이는 $i$ 초에 노래를 부르기 시작한 것이다.

시이는 $0$ 초에 노래를 부르기 시작하고, $1$ 초부터 $N$ 초 직전까지 매초 노래를 다시 부르기 시작할 수 있다.

시이는 노래를 최대 몇 번 부르기 시작할 수 있는가?

첫 번째 줄에 시이가 부르고자 하는 노래를 나타내는 문자열의 길이 $N$ 이 주어진다.

두 번째 줄에 시이가 부르고자 하는 노래를 나타내는 문자열이 주어진다.

첫 번째 줄에 시이가 노래를 시작할 수 있는 최대 횟수를 출력한다.