반복 패턴

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

같은 문자열을 두 번 이상 반복해서 만들 수 있는 문자열은 반복 패턴을 가진다고 말한다. 예를 들어 abdeabde는 abde를 두 번 이상 반복해서 만들 수 있으므로 반복 패턴을 가지며, abcefabce는 같은 문자열을 반복해서 덧붙이는 방식으로는 만들 수 없으므로 반복 패턴을 가지지 않는다.

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

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

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

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

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