시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 (언어별 추가 시간 없음) 1024 MB 52 17 17 60.714%

문제

 현욱은 반복되는 패턴에서 안정감을 느낀다. 그래서 모든 것을 반복되는 형태로 만들고 싶어한다. 현욱은 우선 가지고 있는 모든 책의 텍스트를 반복되는 형태로 만들려고 마음 먹었다.

 동일한 문자열을 두 번이상 반복해서 만들 수 있는 문자열을 반복 패턴을 갖고 있다고 말한다. 예를 들어, abdeabde 같은 경우 abde를 두 번 이상 반복해서 만들 수 있으니 반복 패턴을 갖고 있고, abcefabce 같은 경우 어떻게 해도 동일한 문자열을 반복해서 덧붙이는 방식으로는 만들 수 없으니 반복 패턴을 갖고 있지 않는 문자열이다.

현욱은 책에 적힌 텍스트를 반복되는 패턴으로 만들려고 한다. 기존 문자열의 내용은 책에 인쇄되어 있기 때문에 변경할 수 없지만, 뒤에 종이를 덧붙여서 내용을 추가할 수는 있다. 하지만 너무 많은 글을 추가하면 팔이 아프기 때문에 최대 글자의 문자만 덧붙이려고 한다.

이 때, 책의 텍스트를 반복되는 패턴으로 만들었을 때 그 패턴의 길이가 길 수록 현욱은 만족감을 느낀다. 단, 과도한 변화는 부자연스러우니 패턴의 길이는 최대 N 글자로 한다. 현욱을 도와 어떻게 하면 가장 긴 패턴을 만들 수 있는지 계산해보자.

입력

문자열의 길이 N, 덧붙일 수 있는 문자의 개수 K(1 ≤ N, K ≤ 100,000)가 주어진다.

두번째 줄에 길이 N짜리 영어 소문자로만 이루어진 문자열 S가 주어진다.

출력

K글자 이하의 문자를 덧붙여서 S를 반복되는 패턴으로 만들었을 때 만들어질 수 있는 길이 N 이하의 패턴의 최대 길이를 출력한다. 반복되는 패턴으로 만들 수 없으면 0을 출력한다.

예제 입력 1

8 0
abdeabde

예제 출력 1

4

abdeabde에서 만들 수 있는 반복 패턴은 abde이고 이게 최대 길이이다.

예제 입력 2

5 4
abcde

예제 출력 2

0

예제 입력 3

5 5
abcde

예제 출력 3

5

예제 입력 4

5 3
ababa

예제 출력 4

4

출처

Contest > 웰노운컵 > 제2회 웰노운컵 Day 2 F번