16229번 - 반복 패턴

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

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

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

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

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

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

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