우유 패턴

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

요약

정수 N개가 주어질 때, 겹치는 등장을 포함해 K번 이상 반복되는 가장 긴 연속 부분 수열의 길이를 구한다.

난이도: 어려움10점 중 8점
유형: 문자열 매칭, 이분 탐색, 정렬, 배열
정답자: 아직 제출이 없습니다

문제

농부 John은 자신이 기르는 젖소가 생산하는 우유의 품질이 날마다 달라진다는 것을 알아챘다. 자세히 조사한 결과, 다음 날의 품질을 정확히 예측할 수는 없지만 매일의 우유 품질에 어떤 규칙적인 패턴이 있음을 발견했다.

엄밀한 연구를 위해 그는 각 우유 표본을 $0$ 이상 $1{,}000{,}000$ 이하의 정수로 기록하는 분류 체계를 고안했고, 한 마리 젖소로부터 $N$ 일 동안( $1 \le N \le 20{,}000$ )의 자료를 기록했다. 그는 완전히 똑같은 형태로 최소 $K$ 번( $2 \le K \le N$ ) 반복되는 가장 긴 표본 패턴을 찾으려 한다. 이때 패턴은 서로 겹쳐도 된다. 예를 들어 수열 1 2 3 2 3 2 3 1에서는 2 3 2 3이 두 번 반복된다.

표본 수열이 주어질 때, 이렇게 반복되는 가장 긴 연속 부분수열의 길이를 구하라. 최소 $K$ 번 반복되는 부분수열이 적어도 하나 존재함이 보장된다.

입력

첫째 줄: 공백으로 구분된 두 정수 $N$ 과 $K$ .
둘째 줄부터 $N+1$ 째 줄까지: 한 줄에 하나씩 $N$ 개의 정수. $i$ 번째 줄에는 $i$ 일째 우유의 품질이 주어진다.

출력

첫째 줄: 최소 $K$ 번 나타나는 가장 긴 패턴의 길이를 나타내는 정수 하나.

예제3

예제 1
입력
```
8 2
1
2
3
2
3
2
3
1
```
예상 출력
```
4
```
예제 2
입력
```
5 2
0
0
0
0
0
```
예상 출력
```
4
```
예제 3
입력
```
6 2
1000000
0
1000000
0
1000000
0
```
예상 출력
```
4
```