题意：给一个N项的序列（1<=N <= 20,000，每一项是不超过1,000,000的自然数），求至少出现K次的子串的最大长度，出现位置允许重叠。
CS的模拟赛里的一题。题面里说subsequence，翻译过来是“子序列”。在我的理解中，这个“序列”和LCS问题里的序列一样，是从数列里抽的一根筋。很坑的wnxFinger_Leader同学先是说这是一道KMP，然后告诉我题面里“1 2 3 2 3 2 3 1 重复了2 3 2 3两次”，“两次”前面隐含着“至少”……
于是纠结了一个小时。
如果是子序列就不好做啦。至少，不具备单调性，二分是不可以的。
得知了正确题意，想到了哈希。因为先前的思考，潜意识里否定了二分。经过提醒，才发觉现在不是在做刚才那题啊……
二分最大长度L。验证的时候，取出所有长为L的子串的哈希值，排序，看是否有一个哈希值出现了至少K次。时间复杂度 O(nlg2n) 。
马老师想到了二分+后缀数组，题解亦如此。但是感觉他俩说的又有点不一样……验证的时候遍历height数组，看是否有连续的一段长为K，且值均不小于L。时间复杂度 O(nlgn) 。传送门：WZH学长的题解
在OpenJudge上面，hash这个函数名CE了。
#include <cstdio>
#include <algorithm>
using namespace std;
typedef unsigned long long ll;
const int MAX_N = 1e6, H = 13131;
int n, k, a[MAX_N];
ll h[MAX_N+1], x[MAX_N+1] = {
1};ll Hash(int i, int l)
{return h[i] - h[i+l] * x[l];
}bool check(int l)
{static ll b[MAX_N];int j = 0, ans = 0;for (int i = 0; i+l <= n; ++i)b[j++] = Hash(i, l);sort(b, b+j);for (int i = 0, t; i < j; i = t) {t = i+1;while (t < j && b[i] == b[t])++t;ans = max(ans, t-i);}return ans >= k;
}int main()
{scanf("%d %d", &n, &k);for (int i = 0; i < n; ++i)scanf("%d", &a[i]);for (int i = 1; i <= n; ++i)x[i] = x[i-1] * H;for (int i = n-1; i >= 0; --i)h[i] = h[i+1] * H + a[i];int l = 1, r = n; // [l, r)while (r-l > 1) {int m = (l+r)/2;if (check(m))l = m;elser = m;}printf("%d\n", l);return 0;
}