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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
| #include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
long long read()
{
long long x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
while(isdigit(c)){x=x*10+c-'0';c=getchar();}
return x*f;
}
const int M=1000000+100;
const int N=20000+100;
int s[N],sa[N],id[N],height[N];
long long rank[N];
void CountSort(long long a[],int n,int Exp,int m)
{
static long long cnt[M],b[N];
memset(cnt,0,sizeof cnt);
for(int i=1;i<=n;i++)
cnt[(a[i]/Exp)%m]++;
for(int i=1;i<=m;i++)
cnt[i]+=cnt[i-1];
for(int i=n;i>=1;i--)
{
b[cnt[(a[i]/Exp)%m]]=a[i];
if(Exp==1)
id[cnt[(a[i]/Exp)%m]--]=i;
else
sa[cnt[(a[i]/Exp)%m]--]=id[i];
}
for(int i=1;i<=n;i++)
a[i]=b[i];
}
void RadixSort(long long a[],int n,int m)
{
CountSort(a,n,1,m);
CountSort(a,n,m,m);
}
int n,K,L[N],R[N];
void GetSA()
{
static long long t[N];
for(int i=1;i<=n;i++)
rank[i]=t[i]=s[i];
int m=1000000+1;
for(int k=1;;k=k<<1)
{
for(int i=1;i<=n;i++)
rank[i]=t[i]=rank[i]*m+(i+k<=n?rank[i+k]:0);
RadixSort(t,n,m);
m=0;
for(int i=1;i<=n;i++)
{
if(t[i]!=t[i-1])
m++;
rank[sa[i]]=m;
}
if(m==n) break;
m++;
}
for(int i=1;i<=n;i++)
{
if(rank[i]==1) continue;
int to=max(0,height[rank[i-1]]-1);
for(;sa[rank[i]]+to<=n and sa[rank[i]-1]+to<=n;to++)
if(s[sa[rank[i]]+to]!=s[sa[rank[i]-1]+to])
break;
height[rank[i]]=to;
}
}
int mstack[N],top;
bool Check(int x)
{
for(int i=1;i<=n;i++)
if(height[i]>=x and (R[i]-(L[i]-1)+1)>=K)
return true;
return false;
}
int main()
{
n=read(),K=read();
for(int i=1;i<=n;i++)
s[i]=read();
GetSA();
for(int i=1;i<=n;i++)
{
while(top>0 and height[i]<=height[mstack[top]]) top--;
L[i]=mstack[top]+1;
mstack[++top]=i;
}
mstack[top=0]=n+1;
for(int i=n;i>=1;i--)
{
while(top>0 and height[i]<=height[mstack[top]]) top--;
R[i]=mstack[top]-1;
mstack[++top]=i;
}
int ans=0,l=0,r=n,mid;
while(l<=r)
{
mid=(l+r)/2;
if(Check(mid)==true)
l=mid+1,ans=max(ans,mid);
else
r=mid-1;
}
printf("%d",ans);
return 0;
}
|
这样，我们只需要二分一个答案，然后一路扫过去检查就完事啦(～￣▽￣)～ 时间复杂度$O(nlogn)$,空间复杂度$O(n)$
