[2018 SCPC 본선]
외계인이 존재하는가는 사람들이 오랫동안 궁금해온 문제이다.
김박사는 삼성전자의 후원을 받아서 특정한 별에 외계인이 존재하는지 연구를 진행하고 있다.
이 연구로 외계인을 발견한다면 인류의 모든 지식에 큰 변화가 올 것이다.
이 별이 연구의 대상이 된 이유는 별의 밝기가 매 시간마다 변하기 때문이다.
처음에는 단순한 변광성으로 생각하였지만, 그러기에는 밝기의 변화에 반복이 자주 발생한다는 것을 알아냈기에 현재로서는 이 별에 고도의 문명이 존재하여, 별의 밝기를 조절할 수 있다는 의견이 대다수이다.
고성능 전파망원경 하나가 이 별을 쫓아다니면서 매 시간마다 별의 밝기를 기록한다.
이 밝기는 1 이상 255 이하의 정수로 정규화되어 기록된다.
매 시간 별의 밝기를 기록한 \(N\)개의 정수가 주어졌을 때, 김박사는 이 밝기의 변화가 우연인지 아닌지 알기 위해서 \(X\)번 이상 반복되어 나오는 패턴이 있는지를 효율적으로 찾고 싶어 한다.
예를 들어, \(N = 6\) 이고 2, 1, 4, 1, 4, 1이 전파망원경의 입력이라고 하자.
\(X=2\)라고 하면, 입력 중 두 번 이상 나오는 패턴을 찾아보면 길이가 1인 패턴은 1, 4, 길이가 2인 패턴은 1, 4 그리고 4, 1, 길이가 3인 패턴은 1, 4, 1이다.
김박사의 생각으로는 연속하여 나타나면서 두번 이상 나타나는 가장 긴 패턴이 가장 큰 의미를 갖는다.
따라서 이 경우 답은 1, 4, 1이다.
1, 4, 1이 두 번 나타날때 서로 교차할 수 있는데 주의하라.
\(X=3\)이라면 세 번 이상 반복되어 나온 패턴은 1 뿐이며, \(X=4\)라고 하면 만족하는 패턴이 없다.
구체적으로 어떤 패턴이 나타나는지보다 이 패턴의 길이가 더 의미가 크기 때문에,
\(X=2\)일때 원하는 답은 3 (만족하는 패턴이 1, 4, 1), \(X=3\) 일때 원하는 답은 1 (만족하는 패턴이 1), \(X=4\) 일때 원하는 답은 0 (만족하는 패턴이 없음)이다.
\(N\) 시간의 별의 밝기 측정 값, 패턴의 반복 횟수 \(X\) 가 주어졌을 때, \(X\) 번 이상 반복하여 나타나는 패턴 중 가장 긴 패턴의 길이를 구하는 프로그램을 작성하시오.
입력 파일에는 여러 테스트 케이스가 포함될 수 있다.
파일의 첫째 줄에 테스트 케이스의 개수를 나타내는 자연수 \(T\) 가 주어지고,
이후 차례로 \(T\) 개의 테스트 케이스가 주어진다. (\(1 ≤ T ≤ 50\))
각 테스트 케이스의 첫 줄에는 두 개의 정수 \(N (1≤N ≤50,000)\), \(X (1 ≤X≤N)\)이 순서대로 주어지며 각각은 측정한 별의 밝기 데이터의 크기, 패턴이 나타나야 하는 최소 횟수를 나타낸다.
다음 줄에는 \(N\) 일간 측정한 별의 밝기 데이터가 주어진다.
이는 \(N\)개의 정수로 표현되는데, 각각의 수는 1 이상 255 이하이다.
각 테스트 케이스의 답을 순서대로 표준출력으로 출력하여야 하며,
각 테스트 케이스마다 첫 줄에는 “Case #C”를 출력하여야 한다. 이때 \(C\)는 테스트 케이스의 번호이다.
그 다음 줄에 입력으로 받은 별의 밝기 데이터에서 주어진 횟수 \(X\)이상 나타나는 가장 긴 문자열의 길이를 출력한다.
만약 조건을 만족하는 문자열이 없다면, 숫자 0을 출력한다.
| 입력 |
|---|
| 2 6 2 2 1 4 1 4 1 6 4 2 1 4 1 4 1 |
| 출력 |
|---|
| Case #1 3 Case #2 0 |