POJ - 1743 Musical Theme(不可重叠最长重复子串)

Posted on | In , ,

思路

本题是后缀数组一个常见的应用，不可重叠最长重复子串。后缀数组的基本知识参考SPOJ - SUBST1 New Distinct Substrings一文。对于一个不可重叠最长子串的问题，我们首先对长度二分答案，然后对height数组分段，连续的height值>=k的我们分在一起，然后记录段内sa的最小值和最大值，如果两者的差大于等于k+1（题意要求重复子串之间要有一个字符的间隔）那么现在的k就是符合条件的。需要注意的是这道题卡了cin,cout。

代码

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 <iomanip>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <functional>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
#include <set>
#include <stack>
#include <cctype>
#include <sstream>
#define INF 1e9
#define ll long long
#define ull unsigned long long
#define ms(a,val) memset(a,val,sizeof(a))
#define lowbit(x) ((x)&(-x))
#define lson(x) (x<<1)
#define rson(x) (x<<1+1)

using namespace std;
int n, k;
const int MAX_N = 20010;
int ranks[MAX_N + 1];
int tmp[MAX_N + 1];
inline int read()
{
	int x = 0, f = 1;char ch = getchar();
	while (ch<'0' || ch>'9') { if (ch == '-')f = -1;ch = getchar(); }
	while (ch >= '0'&&ch <= '9') { x = x * 10 + ch - '0';ch = getchar(); }
	return x*f;
}
//倍增计算rank
bool compare_sa(int i, int j) {
	if (ranks[i] != ranks[j])return ranks[i]<ranks[j];
	else {
		int ri = i + k <= n ? ranks[i + k] : -1;
		int rj = j + k <= n ? ranks[j + k] : -1;
		return ri<rj;
	}
}
void construct_sa(int S[], int *sa) {
	//n = strlen(S);
	//对长度为1的字符直接使用ascii码,长度为0的后缀rank值为-1
	for (int i = 0;i <= n;i++) {
		sa[i] = i;
		ranks[i] = i<n ? S[i] : -1;
	}
	for (k = 1;k <= n;k *= 2) {
		sort(sa, sa + n + 1, compare_sa);
		tmp[sa[0]] = 0;
		for (int i = 1;i <= n;i++) {
			tmp[sa[i]] = tmp[sa[i - 1]] + (compare_sa(sa[i - 1], sa[i]) ? 1 : 0);
		}
		for (int i = 0;i <= n;i++) {
			ranks[i] = tmp[i];
		}
	}
}
void construct_lcp(int S[], int *sa, int *lcp) {
	//int n = strlen(S);
	for (int i = 0;i <= n;i++)ranks[sa[i]] = i;
	int h = 0;
	lcp[0] = 0;
	for (int i = 0;i<n;i++) {
		int j = sa[ranks[i] - 1];
		if (h>0)h--;
		for (;j + h<n&&i + h<n;h++) {
			if (S[j + h] != S[i + h])break;
		}
		lcp[ranks[i] - 1] = h;
	}
}
bool judge(int len,int *sa,int *lcp) {
	int mins = n + 5, maxs = -1;
	for (int i = 0;i <= n;i++) {
		if (lcp[i] >= len) {
			mins = min(mins, sa[i]), maxs = max(maxs, sa[i]);
		}
		else {
			mins = min(mins, sa[i]), maxs = max(maxs, sa[i]);
			if (maxs - mins >= len + 1)return true;
			mins = n + 5, maxs = -1;
		}
	}
	return false;
}
int main() {
	//ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	while (scanf("%d",&n)!=EOF) {
		if (n == 0)break;
		int a[MAX_N], diff[MAX_N];
		int lcp[MAX_N + 1], sa[MAX_N + 1];
		ms(lcp, 0), ms(sa, 0), ms(ranks, 0), ms(tmp, 0);
		for (int i = 0;i < n;i++)a[i]=read();
		for (int i = 0;i < n - 1;i++)diff[i] = a[i + 1] - a[i]+88;
		n--;
		construct_sa(diff, sa);
		construct_lcp(diff, sa, lcp);
		int left = 3, right = n / 2,ans;
		while (left <= right) {
			int mid = (left + right)>>1;
			if (judge(mid, sa, lcp))ans = mid,left=mid+1;
			else right = mid - 1;
		}
		if (left == 3)printf("0\n");
		else printf("%d\n",ans+1);
	}
	return 0;
}