poj 1743(二分+后缀数组)

poj 1743

注意用$height$分组如果最后一组最后一个元素在序列末,那么要进行处理!最方便是直接$<=n$,还要注意的是不能重复,而且是$mini+x<maxi$不能是$mini+x<=maxi$

本题求的是长度最少为5的重复子串,并且重复子串可以加上或者减去一个数。我们将数字处理一下取差值,然后直接做,之后再结果$+1$即可

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
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define ms(i, j) memset(i, j, sizeof i)
using namespace std;
const int MAXN = 20000 + 5;
int n, m, a[MAXN], SA[MAXN], tp[MAXN], rk[MAXN], tax[MAXN], height[MAXN];
bool cmp(int *f, int i, int k) {return f[SA[i]]==f[SA[i-1]]&&f[SA[i]+k]==f[SA[i-1]+k];}
void build_SA() {
for (int i=0;i<m;i++) tax[i] = 0;
for (int i=0;i<n;i++) tax[rk[i]=a[i]]++;
for (int i=1;i<m;i++) tax[i] += tax[i-1];
for (int i=n-1;i>=0;i--) SA[--tax[rk[i]]] = i;
int p;
for (int k=1;k<=n;k*=2) {
p = 0;
for (int i=n-k;i<n;i++) tp[p++] = i;
for (int i=0;i<n;i++) if (SA[i]>=k) tp[p++] = SA[i] - k;
for (int i=0;i<m;i++) tax[i] = 0;
for (int i=0;i<n;i++) tax[rk[tp[i]]]++;
for (int i=1;i<m;i++) tax[i] += tax[i-1];
for (int i=n-1;i>=0;i--) SA[--tax[rk[tp[i]]]] = tp[i];
swap(tp, rk), p = 0, rk[SA[0]] = 0;
for (int i=1;i<n;i++) rk[SA[i]] = cmp(tp, i, k) ? p : ++p;
if (++p>=n) break;
m = p;
}
int k = 0;
for (int i=0;i<n;i++) {
if (k) k--;
int j = SA[rk[i]-1];
while (a[i+k]==a[j+k]) k++;
height[rk[i]] = k;
}
}
bool check(int x) {
int maxi , mini;
maxi = mini = SA[1];
for (int i=2;i<=n;i++) {
if (height[i]>=x) {
maxi = max(maxi, SA[i]);
mini = min(mini, SA[i]);
} else {
if (mini+x<maxi) return true;
maxi = mini = SA[i];
}
}
return false;
}
void clear() {}
void init() {
clear();
a[n] = 0;
for (int i=0;i<n;i++) {
scanf("%d", &a[i]);
a[i-1] = a[i] - a[i-1] + 100;
}
a[n-1] = a[n] - a[n-1] + 100;
n++, m = 300;
}
void solve() {
build_SA();
int l = 1, r = n, ans = 0;
while (l<r) {
int mid = (l+r)>>1;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else r = mid;
}
if (ans<4) ans = 0; else ans++;
printf("%d\n", ans);
}
int main() {
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);freopen("1.out", "w", stdout);
#endif
while (scanf("%d", &n)==1&&n) init(), solve();
return 0;
}
------ 本文结束 ------