Re-verse

면접 대비

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

요약

길이 N인 노래 문자열이 주어질 때, 0부터 N-1초 사이에서 겹치는 글자가 서로 어긋나지 않도록 노래를 시작할 수 있는 최대 횟수를 구합니다.

문제

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

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

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

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

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

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

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