农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。
BZOJ_1717_[Usaco2006 Dec]Milk Patterns 产奶的模式_后缀数组
农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查，他发现：虽然他不能预见明天产奶的质量，但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个0到1000000之间的数。并且John记录了N(1<=N<=20000)天的牛奶质量值。他想知道最长的出现了至少K(2<=K<=N)次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当K=2时，这个长度为4。
* Line 1: 两个整数 N,K。
* Lines 2..N+1: 每行一个整数表示当天的质量值。
* Line 1: 一个整数：N天中最长的出现了至少K次的模式的长度
4
先把权值离散化。
二分答案x，转化为判断是否存在一个长度为x的子串在整个字符串中出现了k次，k次可重叠。
把后缀分组，保证任意一个组里任意一个height值都不小于x。
这个长度为x的子串只可能出现在这每个组里。
直接判断是否有一组后缀个数大于等于k即可。
代码：
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 20050
struct A {
int num,id,v;
}a[N];
bool cmp1(const A &x,const A &y){return x.num<y.num;}
bool cmp2(const A &x,const A &y){return x.id<y.id;}
int wa[N],wb[N],ws[N],wv[N],sa[N],r[N],n,m,k;
int rank[N],height[N];
void build_suffix_array() {
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]=r[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=p=1;p<n;j<<=1,m=p) {
for(p=0,i=n-j;i<n;i++) y[p++]=i;
for(i=0;i<n;i++) if(sa[i]-j>=0) 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=p=1;i<n;i++) {
if(y[sa[i]]==y[sa[i-1]]&&y[sa[i]+j]==y[sa[i-1]+j]) x[sa[i]]=p-1;
else x[sa[i]]=p++;
}
}
for(i=1;i<n;i++) rank[sa[i]]=i;
for(i=p=0;i<n-1;height[rank[i++]]=p) {
for(p?p--:0,j=sa[rank[i]-1];r[i+p]==r[j+p];p++);
}
}
bool check(int x) {
if(!x) return 1;
/*int lst=0,i;
for(i=1;i<=n;i++) {
if(height[i]<x) {
if(i-lst>=k) return 1;
lst=i;
}
} */
int cnt=0,i;
for(i=1;i<=n;i++) {
if(height[i]<x) {
if(cnt>=k) return 1;
cnt=1;
}else cnt++;
}
if(cnt>=k) return 1;
return 0;
}
int main() {
scanf("%d%d",&n,&k);
int i,j;
for(i=0;i<n;i++) scanf("%d",&a[i].num),a[i].id=i;
sort(a,a+n,cmp1);
for(i=0,j=0;i<n;i++) {
if(i==0||a[i].num!=a[i-1].num) j++; a[i].v=j;
}
m=j;
sort(a,a+n,cmp2);
for(i=0;i<n;i++) r[i]=a[i].v;
n++;m++;
build_suffix_array();
int l=1,r=n+1;
while(l<r) {
int mid=(l+r)>>1;
if(check(mid)) l=mid+1;
else r=mid;
}
printf("%d\n",l-1);
}
BZOJ_1717_[Usaco2006 Dec]Milk Patterns 产奶的模式_后缀数组
原文：https://www.cnblogs.com/suika/p/8968148.html