P2852 [USACO06DEC]牛奶模式Milk Patterns[后缀数组]

题目描述

农夫John发现他的奶牛产奶的质量一直在变动。经过细致的调查,他发现:虽然他不能预见明天产奶的质量,但连续的若干天的质量有很多重叠。我们称之为一个“模式”。 John的牛奶按质量可以被赋予一个 $0$ 到 $1000000$ 之间的数。并且John记录了 $N(1 \le N \le 20000)$ 天的牛奶质量值。他想知道最长的出现了至少 $K(2 \le K \le N)$ 次的模式的长度。比如1 2 3 2 3 2 3 1 中 2 3 2 3出现了两次。当 $K=2$ 时,这个长度为4。

输入输出格式

输入格式:

Line 1: Two space-separated integers: $N$ and $K$

Lines 2..$N+1$: $N$ integers, one per line, the quality of the milk on day i appears on the ith line.

输出格式:

Line 1: One integer, the length of the longest pattern which occurs at least K times

输入输出样例

输入样例#1:

1
2
3
4
5
6
7
8
9
8 2
1
2
3
2
3
2
3
1

输出样例#1:

1
4

题解

后缀排序的板子就是输出sa数组,所以就不单独发blog了

出现次数大于等于 $k$ ,相当于排序后连续的 $k-1$ 个$h_i$ 的最小值不为0。然后ans就是使最小值最大。

可以二分答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<bits/stdc++.h>
using namespace std;
void qmax(int &x,int y) {if (x<y) x=y;}
void qmin(long long &x,long long y) {if (x>y) x=y;}
int read()
{
char s;
int k=0,base=1;
while((s=getchar())!='-'&&s!=EOF&&!(isdigit(s)));
if(s==EOF)exit(0);if(s=='-')base=-1,s=getchar();
while(isdigit(s)){k=k*10+(s^'0');s=getchar();}
return k*base;
}
void write(int x)
{
if(x<0){putchar('-');write(-x);}
else{if(x/10)write(x/10);putchar(x%10+'0');}
}
const int maxn=40000+200;
const int maxm=1e6+200;
int ch[maxn];
int c[maxn],n,m,x[maxn],y[maxn],s[maxn],p,c1,K;
int rk[maxn],h[maxn];
int l,r,ans;
bool check(int x)
{
int sum=0;
for (int i=1;i<=n;i++)
{
if (h[i]>=x) sum++; else sum=0;
if (sum>=K-1) return true;
}
if (sum>=K-1) return true;
return false;
}
int main()
{
n=read();K=read();
for (int i=1;i<=n;i++) ch[i]=read();
for (int i=1;i<=n;i++) c[x[i]=ch[i]]++,qmax(m,x[i]);
for (int i=1;i<=m;i++) c[i]+=c[i-1];
for (int i=n;i>=1;i--) s[c[x[i]]--]=i;
for (int k=1;k<=n;k<<=1)
{
p=0;//按第二关键字排序
for (int i=n-k+1;i<=n;i++) y[++p]=i;
for (int i=1;i<=n;i++) if (s[i]>k) y[++p]=s[i]-k;
//按第1关键字排序
memset(c,0,sizeof(c));
for (int i=1;i<=n;i++) c[x[y[i]]]++;
for (int i=1;i<=m;i++) c[i]+=c[i-1];
for (int i=n;i>=1;i--) s[c[x[y[i]]]--]=y[i];

memcpy(y,x,sizeof(x));//用之前的x[i]更新排序后的x[i]
p=2;x[s[1]]=1;
for (int i=2;i<=n;i++)//一关键字和二关键字都相同时就不管
x[s[i]]= y[s[i-1]]==y[s[i]]&&y[s[i-1]+k]==y[s[i]+k]?p-1:p++;
if (p>n) break;
m=p;
}
for (int i=1;i<=n;i++) rk[s[i]]=i;
for (int i=1,k=0;i<=n;i++)//h[i]表示排序后第i个串和第i-1个串的lcp
{
if (k) --k;
int j=s[rk[i]-1];
while (ch[i+k]==ch[j+k]) ++k;
h[rk[i]]=k;
}
l=0;r=n;
while (l<=r)//二分答案
{
int mid=(l+r)>>1;
if (check(mid)) {l=mid+1;ans=max(ans,mid);} else r=mid-1;
}
printf("%d\n",ans);
return 0;
}