P2852 [USACO06DEC]Milk Patterns(后缀数组)

题目链接

洛谷

题意简述

给你一个字符串,求最长的出现了至少 $k$ 次的子串的长度。

简要做法

求出 height 数组,若一个长为 $x$ 的子串在原串中出现了至少 $k$ 次,则 height 数组中一定存在至少 $k-1$ 个 连续的大于等于 $x$ 的值。所以,问题就转化成了:求 height 数组中 每连续 $k-1$ 个数的最小值 的最大值。即:$a_i=\min\{height_{i..i+k-2}\}$,求 $a_i$ 的最大值。可以用RMQ/平衡树/线段树/multiset解决。

参考代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <set>

using namespace std;

const int N=40010;

int n,k,a[N],sa[N],rk[N],sa2[N],px[N],cnt[1000010],height[N],ans;
multiset<int> t;

int main()
{
int i,j,w,p,m=1000000;

scanf("%d%d",&n,&k);
--k;

for (i=1;i<=n;++i) scanf("%d",a+i);
for (i=1;i<=n;++i) ++cnt[rk[i]=a[i]];
for (i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for (i=n;i>=1;--i) sa[cnt[rk[i]]--]=i;

for (w=1;w<n;w<<=1,m=p)
{
memset(cnt,0,sizeof(cnt));
for (p=0,i=n;i>n-w;--i) sa2[++p]=i;
for (i=1;i<=n;++i) if (sa[i]>w) sa2[++p]=sa[i]-w;
for (i=1;i<=n;++i) ++cnt[px[i]=rk[sa2[i]]];
for (i=1;i<=m;++i) cnt[i]+=cnt[i-1];
for (i=n;i>=1;--i) sa[cnt[px[i]]--]=sa2[i];
swap(rk,sa2);
for (p=0,i=1;i<=n;++i) rk[sa[i]]=sa2[sa[i]]==sa2[sa[i-1]]&&sa2[sa[i]+w]==sa2[sa[i-1]+w]?p:++p;
}

for (i=1,j=0;i<=n;++i)
{
if (j) --j;
while (a[i+j]==a[sa[rk[i]-1]+j]) ++j;
height[rk[i]]=j;
}

for (i=1;i<=n;++i)
{
t.insert(height[i]);
if (i>k) t.erase(t.find(height[i-k]));
ans=max(ans,*t.begin());
}

cout<<ans;

return 0;
}