洛谷 P2852 [USACO06DEC]Milk Patterns G（后缀数组，height数组）

[USACO06DEC]Milk Patterns G

题目描述

农夫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: 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

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

样例输出 #1

4
1

1、每个数的范围是 0~1e6,  而一共n(<= 2e4) 个数，简单做个离散化


2、出现至少K次意味着后缀排序后有至少连续K个后缀以这个子串作为公共前缀。
	假如当前长度是len， 查看有没有K个子串，长度超过len, 就扫描 height 数组，
	看看是否出现连续 K - 1个 height值 超过 len.

3、 二分 子串的长度 len 就行了
1
2
3
4
5
6
7
8

#include 
using namespace std;
const int M = 2e6 + 10, N = 1e5 + 10;
int a[N];
int mp[M], cnt;

int s[N];	// s[] 数组存放离散化后的数据
int n, m;	//n是后缀个数， m是桶的个数
int K;
int x[N];	//桶数组
int y[N];	//辅助数组
int c[N];	//计数数组
int sa[N];	//sa[k] 表示排名为k的数组后缀编号
int rk[N];	//rk[k] 表示后缀字符串k 的排名
int height[N];	// heght[k] = lcp(sa[i], sa[i - 1])

void get_sa()
{
	int i, k;
	// 按第一个字母排序
	for(i = 1; i <= n; ++i)	// 按第一个字母编桶号， 并累计
		c[(x[i] = s[i])]++;
	for(i = 1; i <= m; ++i)	
		c[i] += c[i - 1];
	for(i = n; i; --i)		//后缀i的排序是i 所在桶号的剩余累计值
		sa[c[x[i]]--] = i;

	for(k = 1; k <= n; k <<= 1)	// logn 轮
	{
		// 按第二关键字排序
		memset(c, 0, sizeof c);
		for(i = 1; i <= n; ++i)	y[i] = sa[i];
		for(i = 1; i <= n; ++i)	c[x[y[i] + k]]++;
		for(i = 1; i <= m; ++i) c[i] += c[i - 1];
		for(i = n; i; i--) sa[c[x[y[i] + k]]--] = y[i];

		//按第一关键字排序
		memset(c, 0, sizeof c);
		for(i = 1; i <= n; ++i)	y[i] = sa[i];
		for(i = 1; i <= n; ++i)	c[x[y[i]]]++;
		for(i = 1; i <= m; ++i)	c[i] += c[i - 1];
		for(i = n; i; --i)	sa[c[x[y[i]]]--] = y[i];

		//把后缀放入桶数组
		for(i = 1; i <= n; ++i)	y[i] = x[i];
		for(m = 0, i = 1; i <= n; ++i)
		{
			if(y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k])
				x[sa[i]] = m;
			else
				x[sa[i]] = ++m;	// 相邻后缀的关键字不相等则放入新桶
		}
		if(m == n)	
			break;
	}
}

// 定理 height[rk[i]] >= height[rk[i - 1]] - 1;
void get_height()
{
	for(int i = 1; i <= n; ++i)
		rk[sa[i]] = i;
	for(int i = 1, k = 0; i <= n; ++i)	//枚举后缀i
	{
		if(rk[i] == 1)	continue;		//第一名height 为0
		if(k) k--;						//上一个后缀的height 值减 1
		int j = sa[rk[i] - 1];			//找出后缀i的前邻后缀 j
		while(i + k <= n && j + k <= n && s[i + k] == s[j + k])
			k++;
		height[rk[i]] = k;
	}
}


// 判断长度为mid 的子串能否出现K 次
bool judge(int mid)
{
	int count = 0;
	for(int i = 2; i <= n; ++i)
	{
		if(height[i] >= mid)
		{
			count++;
			if(count >= K - 1)	// 找到连续K个，长度至少为 mid 的子串
				return true;
		}else{
			count = 0;
		}
	}
	return false;
}

int main()
{
	scanf("%d%d", &n, &K);
	for(int i = 1; i <= n; ++i)
	{
		scanf("%d", &a[i]);
		if(mp[a[i]] == 0)
		{
			mp[a[i]] = ++cnt;
		}
		s[i] = mp[a[i]];
	}
	m = cnt;
	get_sa();
	get_height();	
	int l = 1, r = n;
	while(l < r)
	{
		int mid = (l + r) >> 1;
		if(judge(mid) == false)
		{
			r = mid;	
		}else{
			l = mid + 1;
		}
	}
	printf("%d\n", l - 1);
	return 0;
}
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
116
117
118
119
120
121