题目链接

军火展示:

#include <bits/stdc++.h>
using namespace std;
int n,kkk;
const int N = 20101;
int t1[N],t2[N],sa[N],rank[N],height[N],s[N],c[N];
int x[N],y[N];
int st[N][20];
int m,cnt,len;
int num[N],lq[N];
void srt()
{
	for (int i=1;i<=m;i++)
	    c[i] = 0;
	for (int i=1;i<=n;i++)
	    ++c[x[i]];
	for (int i=1;i<=m;i++)
	    c[i] += c[i-1];
	for (int i=n;i>=1;i--)
	    sa[c[x[y[i]]]--] = y[i],y[i] = 0;
}
void get_SA()
{
	m = 20001;
	for (int i=1;i<=n;i++)
	    x[i] = s[i],y[i] = i;
	srt();
	for (int k=1;k<=n;k<<=1){
		int num = 0;
		for (int i=n-k+1;i<=n;i++)
		    y[++num] = i;
		for (int i=1;i<=n;i++)
		    if (sa[i] > k)
		        y[++num] = sa[i] - k;
	    srt();
	    swap(x,y),num = 1,x[sa[1]] = 1;
	    for (int i=2;i<=n;i++){
	    	x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+k] == y[sa[i-1]+k])?num:++num;
		}
	    if (n == num)
		    break;
		m = num;
	}
}
void get_height()
{
	for (int i=1;i<=n;i++)
	   rank[sa[i]] = i;
	int k = 0;
	for (int i=1;i<=n;i++)
	{
		if (rank[i] == 1)
		    continue;
		int j = sa[rank[i]-1];
		if (k) k--;
		while (i+k <= n && j+k <= n &&s[i+k] == s[j+k]) ++k;
		height[rank[i]] = k;
	}
}//ST
void init()
{
	for (int i=1;i<=n;i++)    st[i][0] = height[i];
	for (int j=1;(1<<j) < n;j++)
	    for (int i=1;i+(1<<j) - 1<=n;i++)
	        st[i][j] = min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int query(int l,int r)
{
	int k = log2(r-l+1);
	return min(st[l][k],st[r-(1<<k)+1][k]);
}
bool check(int length)
{
	int l = 1,r = l+kkk-1;
	while (r <= n){
		int ok = query(l,r);
		if (ok >= length)
		    return true;
		l++,r++;
	}
	return false;
}
int main()
{
	scanf("%d%d",&n,&kkk);
	for (int i=1;i<=n;i++)
	    scanf("%d",&s[i]);
	get_SA();
	get_height();
	init();
	int l = 0,r = n+1;
	while (l+1!=r)
	{
		int mid = (l+r)/2;
		if (check(mid))
		    l = mid;
		else r = mid;
	}
	cout<<l;
	return 0;
}