poj 1743 Musical Theme 二分答案+后缀数组

缘起

楼教主的男人八题 poj 1743 Musical Theme

分析

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
给定一个正整数N(N<=20000)，然后是N个整数xi，(1<=xi<=88, 1<=i<=N)组成一个有序的整数序列；
问这个序列中存在的最长一个符合条件的下标连续的子序列长度是多少，符合的条件是
1、子序列A长度至少为5；
2、有另外一个子序列B，且A、B二者没有相交部分（即不存在xi同时在A，B里出现，这里针对下标而言，A，B的元
素在整个序列里下标都不一样）；
3、A，B的长度一样，设x[i],…x[i+k]，x[j],…x[j+k]，那么要求(x[j]-x[i])=(x[j+1]-x[i+1])=…=
(x[i+k],x[j+k]);即按下标对应的元素差值要相等，差值可以是0，1，2，-1，-2……；当然，为了满足2，(i+k)
<j或者i>(j+k)，为了满足1，k>=4;

举例说明：
例1：1  3  5  3  5  7 答案是3，（对应差值是2，如果是3  5和3  5对应，则长度是2，
求的是存在的最长长度）
例2：1  2  3  4  1  2  3  4答案是4，（对应差值是0）
例3：2  2  2  2  2  2  2  2答案是4；（对应差值是0）

如果找到了最长的长度大于或等于5则输出之，否则全部输出0，所以上面三个例子都应该输出0.

【输入】
多样例. 每个样例第一行是n, 然后n个整数, 最后的样例n是0

【输出】
每个样例输出最长的下标连续的子序列长度

【样例输入】
30
25 27 30 34 39 45 52 60 69 79 69 60 52 45 39 34 30 26 22 18
82 78 74 70 66 67 64 60 65 80
0

【样例输出】
5

【限制】
1s 30MB

【来源】
楼教主男人八题

本题的标准解法是二分答案+SA（在罗大神09年IOI论文P18页中的解法）. 二分答案自然不消说~ 毕竟20000的数据规模摆在那儿，而且本题的答案显然是具备单调性的. 所以二分是不难想到的思路. 那么如何转换为后缀数组呢?

首先, 处理出来原数组的一阶差分数组.——即r[i]=a[i+1]-a[i], 0<=i<n-1, 如果在r中存在重复次数>=2并且重复出现的位置不重叠的的子串的话, 则我们就可以断定，原串a中就存在长度为k的不重叠的子串。

所以，我们将问题转换为求r中最长的不可重叠的重复子串（所谓重复，指的是至少重复2次）.

然后因为本题采用二分答案, 所以本题转换为了判定问题——问r中是否存在长度为k的不重叠的重复子串. 如果存在的话, 则继续判断k+1是否>=5, 亦即k是否>=4, 如果成立的话, 则k+1就是答案, 如果k<4, 则输出0作为答案.

而不重叠的重复子串问题 在【1】中是已经处理过了的. 那里虽然使用的是后缀树作为工具. 但是不也是和后缀打交道吗? 关键是是【1】中是如何利用后缀判定不重叠的. 放到本题, 就是如果r的两个后缀的lcp>=k, 并且这两个后缀的长度之差>=k的话, 则r中就存在长度为k的重复子串（并且出现的位置还不重叠）.

所以罗大神的论文中指出应该使用lcp数组将所有的后缀进行分类. 即对于给定的k, 将后缀之间的LCP>=k的归为一组（复杂度On可以办到）, 然后只需要判断是否存在一组，这组中存在两个后缀长度之差>=k? 这通过sa很好判定——只需要维护这一组的后缀中的sa的最大值和最小值, 然后判定这一组中的sa的最大值减去sa的最小值是否>=k即可. 如果是的话, 则说明存在长度>=k的重复但出现位置不重叠的子串，此时二分答案中的check函数返回true.

一图胜千言

例如 aabaaaab 这个字符串的后缀总共8个, k=2, 按照LCP>=2的标准, 则就分成了如上的四组, 我们要求在每组中的后缀中的最大的sa值和最小的sa值之差>=k, 例如第一组一共4个后缀, 从上到下， 他们的sa值分别是3、4、5、0

则这一组的最大的sa是5， 最小的sa是0，差距是5>=2, 所以存在长度为2的重复不重叠子串, 事实上, aab就是一个.（aab分别是从上至下第三个和第四个后缀的前缀.）

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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
//#include "stdafx.h"
#include <stdio.h>
#include <ctype.h>
#include <algorithm>
#include <string.h>
using namespace std;
//#define LOCAL

const int maxn = 20005, inf = 0x3f3f3f3f;
int n,k, a[maxn], r[maxn],s[maxn], t[maxn], sa[maxn], lcp[maxn];

void read(int &x)
{
	x =0;
	int f = 1;
	char c = getchar();
	while(!isdigit(c))
	{
		if (c=='-')
		{
			f = -1;
		}
		c = getchar();
	}
	while(isdigit(c))
	{
		x = x*10+(c^48);
		c = getchar();
	}
	x *= f;
}

void write(int x)
{
	if (x<0)
	{
		putchar('-');
		x = -x;
	}
	if (x>9)
	{
		write(x/10);
	}
	putchar(x%10+'0');
}

bool c0(int i, int j)
{
	if (r[i]!=r[j])
	{
		return r[i]<r[j];
	}
	int ri = i+k<=n?r[i+k]:-1, rj = j+k<=n?r[j+k]:-1;
	return ri<rj;
}

void da()
{
	k = 1;
	for (int i = 0; i<n;i++)
	{
		sa[i] = i;
	}
	r[n] = 0, sa[n] = n;
	while(k<=n)
	{
		sort(sa, sa+n+1, c0);
		t[sa[0]] = 0;
		for (int i = 1;  i<=n; i++)
		{
			t[sa[i]] = t[sa[i-1]]+c0(sa[i-1], sa[i]);
		}
		memcpy(r,t,(n+1)*sizeof(int));
		k<<=1;
	}
}

void height()
{
	int h =0;
	for (int i = 0,j;i<n;i++)
	{
		if (r[i]==1)
		{
			continue;
		}
		j = sa[r[i]-1];
		if (h)
		{
			--h;
		}
		while(i+h<n && j+h<n)
		{
			if (s[i+h]!=s[j+h])
			{
				break;
			}
			++h;
		}
		lcp[r[i]-1] = h;
	}
}

bool ck(int x) // 是否存在长度>=x的不重叠的重复子串? lcp[1,..,n-1], lcp[i] 是 S[sa[i],...] 和 S[sa[i+1],...] 之间的LCP
{
	int minsa = inf, maxsa = -inf;
	for (int i = 1; i<n; i++)
	{
		if (lcp[i]<x) // 如果到达了另一个组
		{
			minsa = maxsa = sa[i+1];
		}
		else // 如果还没有到达另一个组
		{
			minsa = min(minsa, sa[i]);
			minsa = min(minsa, sa[i+1]);
			maxsa = max(maxsa, sa[i]);
			maxsa = max(maxsa, sa[i+1]);
		}
		if (maxsa - minsa>=x)
		{
			return true;
		}
	}
	return false;
}

int sol() // 二分答案
{
	int lo = 0, hi = n>>1, ans = 0, mid;
	while(lo<=hi)
	{
		mid = lo+hi>>1;
		if (ck(mid))
		{
			ans = mid;
			lo = mid+1;
		}
		else
		{
			hi = mid-1;
		}
	}
	return ans>=4?ans+1:0;
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	while(read(n), n)
	{
		for (int i = 0; i<n; i++)
		{
			read(a[i]);
			if (i)
			{
				r[i-1] = a[i]-a[i-1]; // r[i] 的取值范围是[-87, 87]
			}
		} // 处理出a的一阶差分数组r
		if (n<10)
		{
			write(0);
			puts("");
			continue;
		} // 平凡情形
		memcpy(s,r, sizeof(r)); // s就是da+height模板中的s（即字符串数组）
		--n; // r的长度其实是n-1, 为了方便套da模板, 将n--
		da();
		height();
		write(sol());
		puts("");
	}
	return 0;
}

ac情况（水过水过~）

Status Accepted
Time 454ms
Memory 768kB
Length 2375
Lang G++
Submitted 2019-10-13 19:04:10
RemoteRunId 20956650

参考

【1】https://yfsyfs.github.io/2019/08/03/hdu-3518-Boring-counting-%E5%90%8E%E7%BC%80%E6%A0%91/