「TJOI2016&HEOI2016」字符串

发表于

问题描述

佳媛姐姐过生日的时候，她的小伙伴从某东上买了一个生日礼物。生日礼物放在一个神奇的箱子中。箱子外边写了一个长为 $ n $ 的字符串 $ s $，和 $ m $ 个问题。佳媛姐姐必须正确回答这 $ m $ 个问题，才能打开箱子拿到礼物，升职加薪，出任 CEO，嫁给高富帅，走上人生巅峰。每个问题均有 $a, b, c, d$ 四个参数，问你子串
$s[a \ldots b]$ 的所有子串和 $s[c \ldots d]$ 的最长公共前缀的长度的最大值是多少？佳媛姐姐并不擅长做这样的问题，所以她向你求助，你该如何帮助她呢？

算法讨论

首先二分一个答案$mid$，问题变为判定$[a,b-mid+1]$区间内的后缀与后缀$c$的ＬＣＰ是否$\ge mid$

首先把后缀数组的那几样东西都求出来，要满足某后缀$x$与后缀$c$的ＬＣＰ大于某值，就要满足$rank[x]$与$rand[c]$之间的$height$的最小值比它大，我们倍增得往$c$两侧扩展，得到一个满足条件的区间$[L,R]$，也就是说$rank$在$[L,R]$之间的后缀都满足条件，于是我们只需要知道$[a,b-mid+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
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
#include <stdio.h>
#include <algorithm>
using namespace std;
const int N = 100005;

char buf[1 << 20], *p1, *p2;
#define GC (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? 0 : *p1 ++)
inline int _R() {
	int d; char t;
	while (t = GC, t < '0' || t > '9') ;
	d = t - '0';
	while (t = GC, t >= '0' && t <= '9') d = (d << 3) + (d << 1) + t - '0';
	return d;
}
inline int _S(char *c) {
	char *t = c, ch;
	while (ch = GC, ch == ' ' || ch == '\n' || ch == '\r') ;
	*t ++ = ch;
	while (ch = GC, ch != ' ' && ch != '\n' && ch != '\r') *t ++ = ch;
	*t = 0;
	return t - c;
}

int n, m;
char str[N];
int f[N][19], ws[N], rk[N], ht[N], wv[N], sa[N], wa[N], wb[N];

const int ALPHA = 255;
void DA(int n) {
	str[n - 1] = 0;
	int i, j, k, p, m = ALPHA, *x = wa, *y = wb, *t;

	for (i = 0; i < n; i ++) ws[x[i] = str[i]] ++;
	for (i = 1; i < m; i ++) ws[i] += ws[i - 1];
	for (i = n - 1; i >= 0; i --) sa[-- ws[x[i]]] = i;

	for (j = 1, p = 1; p < n; j <<= 1, m = p) {
		for (p = 0, i = n - j; i < n; i ++) y[p ++] = i;
		for (i = 0; i < n; i ++) if (sa[i] >= j) y[p ++] = sa[i] - j;

		for (i = 0; i < n; i ++) wv[i] = x[y[i]];
		for (i = 0; i < m; i ++) ws[i] = 0;

		for (i = 0; i < n; i ++) ws[wv[i]] ++;
		for (i = 1; i < m; i ++) ws[i] += ws[i - 1];
		for (i = n - 1; i >= 0; i --) sa[-- ws[wv[i]]] = y[i];

		for (t = x, x = y, y = t, p = 1, x[sa[0]] = 0, i = 1; i < n; i ++)
			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + j] == y[sa[i - 1] + j]) ? p - 1 : p ++;
	}

}
void calH() {
	int i, j, k;
	for (i = 1; i <= n; i ++) rk[sa[i]] = i;
	for (i = 0, k = 0; i < n; ht[rk[i ++]] = k)
		for (k ? k -- : 0, j = sa[rk[i] - 1]; str[i + k] == str[j + k]; k ++);
	for (i = n; i >= 1; i --) rk[i] = rk[i - 1];

	for (i = 1; i <= n; i ++) f[i][0] = ht[i];
	for (j = 1; j <= 18; j ++)
		for (i = 1; i + (1 << j - 1) <= n; i ++)
			f[i][j] = min(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);
}

struct Node {
	Node *Son[2];
	int sum;
} pool[10000000], *null, *tl, *root[N];

void _init() {
	null = tl = pool;
	null -> Son[0] = null -> Son[1] = null;
	for (int i = 0; i <= n; i ++) root[i] = null;
}

Node* _copy(Node *p) {
	Node *x = ++ tl;
	x -> Son[0] = p -> Son[0];
	x -> Son[1] = p -> Son[1];
	x -> sum = p -> sum;
	return x;
}

void _pushup(Node *p) {
	p -> sum = p -> Son[0] -> sum + p -> Son[1] -> sum;
}

void _modify(Node *&p, Node *x, int l, int r, int k) {
	p = _copy(x);
	if (l == r) { p -> sum ++; return; }
	int mid = l + r >> 1;
	if (k <= mid) _modify(p -> Son[0], x -> Son[0], l, mid, k);
	else _modify(p -> Son[1], x -> Son[1], mid + 1, r, k);
	_pushup(p);
}

int _query(Node *p, int l, int r, int x, int y) {
	if (x <= l && r <= y) return p -> sum;
	int mid = l + r >> 1, sum = 0;
	if (x <= mid) sum += _query(p -> Son[0], l, mid, x, y);
	if (mid < y) sum += _query(p -> Son[1], mid + 1, r, x, y);
	return sum;
}

int a, b, c, d;
bool check(int x) {
	int i, j, k, l, r;
	l = r = rk[c];
	for (i = 18; i >= 0; i --)
		if (l - (1 << i) >= 1 && f[l - (1 << i) + 1][i] >= x)
			l -= 1 << i;
	for (i = 18; i >= 0; i --)
		if (r + (1 << i) <= n && f[r + 1][i] >= x)
			r += 1 << i;
	return _query(root[b - x + 1], 1, n, l, r) - _query(root[a - 1], 1, n, l, r) > 0;
}

int main() {
	// freopen("str1.in", "r", stdin);
	int i, j, k, l, r, mid, ans;
	n = _R(), m = _R();
	_S(str);
	DA(n + 1);
	calH();

	_init();
	for (i = 1; i <= n; i ++)
		_modify(root[i], root[i - 1], 1, n, rk[i]);

	for (i = 1; i <= m; i ++) {
		a = _R(), b = _R(), c = _R(), d = _R();
		
		l = 1, r = min(d - c + 1, b - a + 1), ans = 0;
		while (l <= r) {
			mid = l + r >> 1;
			if (check(mid)) l = mid + 1, ans = mid;
			else r = mid - 1;
		}
		printf("%d\n", ans);
	}
}