P2852 [USACO06DEC] Milk Patterns G

题目描述

农夫约翰注意到他的奶牛所产的牛奶质量每天都在变化。经过进一步调查，他发现虽然无法预测牛奶质量从一天到下一天的变化，但每天的牛奶质量中存在一些规律模式。

为了进行严格的研究，他发明了一种复杂的分类方案，其中每个牛奶样本被记录为一个介于 $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$ 次。

输入格式

第 $1$ 行：两个用空格分隔的整数：$N$ 和 $K$。

第 $2$ 行到第 $N+1$ 行：$N$ 个整数，每行一个，第 $i$ 行表示第 $i$ 天的牛奶质量。

输出格式

第 $1$ 行：一个整数，表示至少出现 $K$ 次的最长子串的长度。

输入输出样例 #1

输入 #1

8 2
1
2
3
2
3
2
3
1

输出 #1

4

说明/提示

题面翻译由 ChatGPT-4o 提供。