Posts Tagged ‘RMQ’

POJ 2758 Checking the Text

Posted in PKU OJ on 四月 22nd, 2010 by 纳米 – Be the first to comment

2010-04-16(17?)，阅读题目、题解
2010-04-18、19、20，代码实现，发现理解错题
2010-04-21，代码改写
2010-04-22，发现错误，再改，AC

这道题挺难的，其实也不是很难，就是很麻烦，做完再看，其实也一般般了，不过拖了那么长时间，估计在比赛遇到我打死也不会写这样的题目……

解题报告：

1. 首先需要理解好题目的意思，插入操作的位置是对应当前位置的，而查询操作的位置是对应原始位置的，我就是在这里看错题，发现相当恶心。本来打算把所有的位置转换成原始位置处理，发现不好做，于是统一储存和利用当前位置来计算。

2. 如果没有插入操作，就是经典的LCP问题，用O(n log2 n)的后缀数组，O(n log2 n) – O(n)的RMQ即可顺利解决，于是迅速敲出后缀数组和RMQ。

3. 但是有插入操作，按照POJ的解题报告，视作插入原字符串的空隙即可。好了，所有的麻烦就在这里了。大概这样做（w0, w1为两个位置指针）：
(1) 判断要比较的两个位置是否为空隙（or），是转(2)，否转(3)；
(2) 如果对应的两个字符相同，则ans++、w0++、w1++，转(1)，否则跳出；
(3) 计算l = LCP，然后与下一个空隙比较，如果[w0, w0 + l)和[w1, w1 + l)其中一个有空隙，则把l缩小到相应的位置，且ans、w0、w1均增加l；若不存在空隙，ans增加l，并跳出。

4. 时间复杂度分析：设总长度为L，插入操作数A，查询操作数B：后缀数组：O(L log2 L)，RMQ初始化：O(L log2 L)，插入操作：O(A*A)，查询操作：O(A*B)。综上，总时间复杂度为O(L log2 L + A^2 + AB)。比POJ给出解题报告略低，但实现效果一般，2500+ms。

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
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205

#include <stdio.h>
#include <string.h>
 
const int maxn = 50205, maxm = 20203, maxins = 203, maxlogn = 16;
int n, m, operate[maxm][3], sa[maxn], rank[maxn], height[maxn];
int rmq_arr[maxlogn][maxn], pow[maxlogn], fpow[maxn], insert[maxins][2], insert_n;
char words[maxn];
 
int input() {
	scanf("%s%d", words, &m);
	for (int i = 1; i <= m; ++i) {
		char ch = 0;
		while (ch != 'Q' && ch != 'I')
			scanf("%c", &ch);
		if (ch == 'Q') {
			operate[i][0] = 0;
			scanf("%d%d", &operate[i][1], &operate[i][2]);
			--operate[i][2], --operate[i][1];
		} else {
			operate[i][0] = 1;
			ch = 0;
			while ((ch < 'A' || ch > 'Z') && (ch < 'a' || ch > 'z'))
				scanf("%c", &ch);
			operate[i][1] = ch;
			scanf("%d", &operate[i][2]);
			--operate[i][2];
		}
	}
	n = strlen(words);
	return 0;
}
 
int build_suffix() {
	int st[maxn], arr1[maxn], arr2[maxn];
	int m = 'z', *sy = arr1, *ra = arr2;
	memset(st, 0, sizeof(st));
	for (int i = 0; i <= n; ++i)
		++st[(int)words[i]];
	for (int i = 1; i <= m; ++i)
		st[i] += st[i - 1];
	for (int i = n; i >= 0; --i)
		sa[--st[(int)words[i]]] = i;
	ra[sa[0]] = m = 0;
	for (int i = 1; i <= n; ++i)
		ra[sa[i]] = words[sa[i]] == words[sa[i-1]] ? m : ++m;
	for (int l = 1; m < n; l += l) {
		int j = 0, *t;
		for (int i = n+1-l; i <= n; ++i)
			sy[j++] = i;
		for (int i = 0; i <= n; ++i)
			if (sa[i] >= l)
				sy[j++] = sa[i] - l;
		memset(st, 0, sizeof(st));
		for (int i = 0; i <= n; ++i)
			++st[ra[i]];
		for (int i = 1; i <= m; ++i)
			st[i] += st[i - 1];
		for (int i = n; i >= 0; --i)
			sa[--st[ra[sy[i]]]] = sy[i];
		sy[sa[0]] = m = 0;
		for (int i = 1; i <= n; ++i)
			sy[sa[i]] = ra[sa[i]]==ra[sa[i-1]] && ra[sa[i]+l]==ra[sa[i-1]+l] ? m : ++m;
		t = sy;
		sy = ra;
		ra = t;
	}
	memcpy(rank, ra, sizeof(rank));
	return 0;
}
 
int calc_height() {
	for (int i = 0, p = 0; i < n; ++i, p?--p:0) {
		int j = sa[rank[i]-1];
		while (words[i + p] == words[j + p])
			++p;
		height[rank[i]] = p;
	}
	return 0;
}
 
int min(int x, int y) {
	return x < y ? x : y;
}
 
int calc_rmq() {
	for (int i = 1; i <= n; ++i)
		rmq_arr[0][i] = height[i];
	for (int i = 1, l = 1; l < n; ++i, l += l) {
		for (int j = 1; j + l <= n; ++j)
			rmq_arr[i][j] = min(rmq_arr[i-1][j], rmq_arr[i-1][j+l]);
		for (int j = n-l+1; j <= n; ++j)
			rmq_arr[i][j] = rmq_arr[i-1][j];
	}
	return 0;
}
 
int calc_fpow() {
	int pow0 = 1, pow1 = 2, pows = 0;
	fpow[1] = 0;
	do {
		for (int i = pow0 + 1; i <= pow1; ++i)
			fpow[i] = pows;
		pow[pows++] = pow0;
		pow0 = pow1;
		pow1 = min(n, pow0 << 1);
	} while (pow0 < n);
	return 0;
}
 
int rmq(int left, int right) {
	int k = fpow[right - left + 1];
	return min(rmq_arr[k][left], rmq_arr[k][right - pow[k] + 1]);
}
 
int lcp(int w0, int w1) {
	return rank[w0] < rank[w1] ? rmq(rank[w0]+1, rank[w1]) : rmq(rank[w1]+1, rank[w0]);
}
 
int nowpos(int key) {
	int w = 0;
	while (w < insert_n && insert[w+1][0] - w <= key)
		++w;
	return key + w;
}
 
int find_query(int p, int key) {
	int res = p;
	while (res < insert_n && insert[res+1][0] <= key)
		++res;
	return res;
}
 
int work_query(int w0, int w1) {
	if (w0 == w1)
		return n + insert_n - w0;
	int p0 = 0, p1 = 0, c0, c1;
	int res = 0, l;
	while (1) {
		p0 = find_query(p0, w0);
		p1 = find_query(p1, w1);
		if (insert[p0][0] == w0 || insert[p1][0] == w1) {
			c0 = insert[p0][0] == w0 ? insert[p0][1] : (int)words[w0 - p0];
			c1 = insert[p1][0] == w1 ? insert[p1][1] : (int)words[w1 - p1];
			if (c0 == c1) {
				++w0, ++w1;
				++res;
			} else {
				break;
			}
		} else {
			l = lcp(w0 - p0, w1 - p1);
			if (p0 < insert_n)
				l = min(l, insert[p0+1][0] - w0);
			if (p1 < insert_n)
				l = min(l, insert[p1+1][0] - w1);
			if (l > 0) {
				w0 += l;
				w1 += l;
				res += l;
			} else {
				break;
			}
		}
	}
	return res;
}
 
int find_insert(int p, int key) {
	int res = 0;
	while (res < insert_n && insert[res+1][0] < key)
		++res;
	return res;
}
 
int work_insert(int w, int ch) {
	int p = find_insert(0, w) + 1;
	memmove(insert[p+1], insert[p], (int)insert[insert_n+1] - (int)insert[p]);
	++insert_n;
	insert[p][0] = w;
	insert[p][1] = ch;
	for (int j = p+1; j <= insert_n; ++j)
		++insert[j][0];
	return 0;
}
 
int work() {
	insert[0][0] = insert[1][0] = -1;
	for (int i = 1; i <= m; ++i)
		if (operate[i][0] == 0) {
			printf("%d\n", work_query(nowpos(operate[i][1]), nowpos(operate[i][2])));
		} else {
			work_insert(operate[i][2], (int)operate[i][1]);
		}
	return 0;
}
 
int main() {
	input();
	build_suffix();
	calc_height();
	calc_rmq();
	calc_fpow();
	work();
	return 0;
}