두 번 나타나는 부분 문자열

시간 제한6초메모리 제한128 MB

요약

문자열과 최대 K번의 문자 교체가 주어질 때, 서로 다른 두 위치에서 겹침을 허용하며 나타나는 가장 긴 부분 문자열의 길이를 최대로 만드는 값을 구한다.

문제

영어 소문자로 이루어진 문자열 $S$ 가 있다.

먼저 다음 값을 정의한다. $S$ 안에서 서로 다른 두 시작 위치에 나타나는 부분 문자열 중 가장 긴 것의 길이다. 두 등장 구간은 겹쳐도 된다. 그런 부분 문자열이 하나도 없으면 이 값은 $0$ 이다.

이제 $S$ 의 글자를 다른 소문자로 바꿀 수 있고, 바꾸기는 최대 $K$ 번까지 할 수 있다. 바꾸기를 모두 끝낸 문자열에서 위 값을 계산한다. 이 값을 가장 크게 만들었을 때의 값을 구하여라.

바꾸기는 문자열에 한 번만 적용된다. 두 등장 구간이 겹치면 겹친 자리의 글자는 두 등장에 함께 쓰인다.

첫째 줄에 정수 $K$ 가 주어진다. ( $0 \le K \le 5000$ )

둘째 줄에 영어 소문자로만 이루어진 문자열 $S$ 가 주어진다. ( $1 \le |S| \le 5000$ )

최대 $K$ 번의 변경으로 얻을 수 있는 가장 큰 값을 정수 하나로 출력한다.

$K = 1$ 이고 $S$ 가 abcba인 경우를 보자. 세 번째 글자 c를 a로 바꾸면 문자열은 ababa가 되고, 부분 문자열 aba가 0번 위치와 2번 위치에 나타난다. 답은 3이다.