记录编号	213879	评测结果	AAAAAAAAAA
题目名称	[USACO Dec06]产奶的模式	最终得分	100
用户昵称	assassain	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-12-13 17:17:41	内存使用	4.72 MiB

#define MAXN 20010UL
#include <cstdio>

using namespace std;

int hd, tl, ans, sa[MAXN], rk[MAXN], wa[MAXN], wb[MAXN], wv[MAXN], w[MAXN], lie[MAXN], ht[MAXN], ws[1000010];

bool CP(int *r,int x,int y, int l) {
	return r[x]==r[y]&&r[x+l]==r[y+l];
}

void HZ(int *w,int *sa,int n,int m) {
	int i, j, p, *x = wa, *y = wb, *t;
	for(i = 0 ; i <= m ; ++ i) ws[i] = 0;
	for(i = 0 ; i < n ; ++ i) ++ ws[x[i] = w[i]];
	for(i = 1 ; i <= m ; ++ i) ws[i] += ws[i-1]; 
	for(i = n-1 ; i >= 0 ; -- i) sa[-- ws[x[i]]] = i;
	for(j = 1, p = 1 ; p < n ; j *= 2, m = p) {
		for(p = -1, i = n-j ; i < n ; ++ i) y[++ p] = i;
		for(i = 0 ; i < n ; ++ i) if(sa[i] >= j) y[++ p] = sa[i]-j;
		for(i = 0 ; i < n ; ++ i) wv[i] = x[y[i]];
		for(i = 0 ; i <= m ; ++ i) ws[i] = 0;
		for(i = 0 ; i < n ; ++ i) ++ ws[wv[i]];
		for(i = 1 ; i <= m ; ++ i) ws[i] += ws[i-1];
		for(i = n-1 ; i >= 0 ; -- i) sa[-- ws[wv[i]]] = y[i];
		for(t = x, x = y, y = t, x[sa[0]] = 0, i = 1, p = 1 ; i < n ; ++ i)
			x[sa[i]] = CP(t, sa[i], sa[i-1], j)?p-1:p++;
	}
}

void HT(int n) {
	int i, j, k = 0;
	for(i = 0 ; i <= n ; ++ i) rk[sa[i]] = i;
	for(i = 0 ; i < n ; ht[rk[i ++]] = k)
		for(k?--k:0, j = sa[rk[i]-1]; w[i+k]==w[j+k] ; ++ k);
	return;
}

int main() {
	freopen("patterns.in", "r", stdin);
	freopen("patterns.out", "w", stdout);
	int n, k, mx = 0;
	scanf("%d%d", &n, &k);
	for(int i = 0 ; i < n ; ++ i) {
		scanf("%d", &w[i]);
		if(mx<w[i]) mx = w[i];
	}
	HZ(w, sa, n+1, mx);
	HT(n);
	for(int i = 2 ; i < k ; ++ i) {
		while(hd<tl&&ht[lie[tl-1]]>ht[i]) -- tl;
		lie[tl ++] = i;
	}
	for(int i = k ; i <= n ; ++ i) {
		while(hd<tl&&lie[hd]<=i-k+1) ++ hd;
		while(hd<tl&&ht[lie[tl-1]]>ht[i]) -- tl;
		lie[tl ++] = i;
		if(ans<ht[lie[hd]]) ans = ht[lie[hd]];
	}
	printf("%d", ans);
	return 0;
}