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
| #include <iostream>
#define maxn 100010
using namespace std;
int n, m;
char s[maxn];
int tax[maxn], tp[maxn], sa[maxn], rk[maxn], M = 255;
void rsort() {
for (int i = 0; i <= M; ++i) tax[i] = 0;
for (int i = 1; i <= n; ++i) ++tax[rk[i]];
for (int i = 1; i <= M; ++i) tax[i] += tax[i - 1];
for (int i = n; i; --i) sa[tax[rk[tp[i]]]--] = tp[i];
}
int H[maxn];
void init_sa() {
if (n == 1) return sa[1] = rk[1] = 1, void(); int cnt = 1;
for (int i = 1; i <= n; ++i) rk[i] = s[i], tp[i] = i; rsort();
for (int k = 1; k < n; k *= 2) {
if (cnt == n) break; M = cnt; cnt = 0;
for (int i = n - k + 1; i <= n; ++i) tp[++cnt] = i;
for (int i = 1; i <= n; ++i) if (sa[i] > k) tp[++cnt] = sa[i] - k;
rsort(); swap(rk, tp); rk[sa[1]] = cnt = 1;
for (int i = 2; i <= n; ++i) {
if (tp[sa[i - 1]] != tp[sa[i]] || tp[sa[i - 1] + k] != tp[sa[i] + k]) ++cnt;
rk[sa[i]] = cnt;
}
} int lcp = 0;
for (int i = 1; i <= n; ++i) {
if (lcp) --lcp;
int j = sa[rk[i] - 1];
while (s[j + lcp] == s[i + lcp]) ++lcp;
H[rk[i]] = lcp;
}
}
int Log[maxn], st[maxn][21];
void init_st() { Log[0] = -1;
for (int i = 1; i <= n; ++i) Log[i] = Log[i >> 1] + 1, st[i][0] = H[i];
for (int j = 1; j <= 20; ++j)
for (int i = 1; i + (1 << j) - 1 <= n; ++i)
st[i][j] = min(st[i][j - 1], st[i + (1 << j - 1)][j - 1]);
}
int lcp(int l, int r) {
if (++l > r) return n - sa[r] + 1;
int k = Log[r - l + 1];
return min(st[l][k], st[r - (1 << k) + 1][k]);
}
#define lc T[i].ch[0]
#define rc T[i].ch[1]
#define Lc T[j].ch[0]
#define Rc T[j].ch[1]
struct zhuxi {
int v, ch[2];
} T[maxn * 20]; int rt[maxn], top;
void update(int &i, int j, int l, int r, int k, int v) {
i = ++top; T[i] = T[j]; T[i].v += v;
if (l == r) return ; int m = l + r >> 1;
if (k <= m) update(lc, Lc, l, m, k, v);
else update(rc, Rc, m + 1, r, k, v);
}
int query(int i, int j, int l, int r, int L, int R) {
if (l > R || r < L) return 0;
if (L <= l && r <= R) return T[j].v - T[i].v;
int m = l + r >> 1;
return query(lc, Lc, l, m, L, R) + query(rc, Rc, m + 1, r, L, R);
}
bool check(int x, int a, int b, int c) {
int l = 1, r = rk[c], mid, L, R;
while (l <= r) {
mid = l + r >> 1;
if (lcp(mid, rk[c]) >= x) L = mid, r = mid - 1;
else l = mid + 1;
}
l = rk[c]; r = n;
while (l <= r) {
mid = l + r >> 1;
if (lcp(rk[c], mid) >= x) R = mid, l = mid + 1;
else r = mid - 1;
}
return query(rt[a - 1], rt[b - x + 1], 1, n, L, R) > 0;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> s + 1; init_sa(); init_st();
for (int i = 1; i <= n; ++i) update(rt[i], rt[i - 1], 1, n, rk[i], 1);
for (int i = 1; i <= m; ++i) {
int a, b, c, d; cin >> a >> b >> c >> d;
int l = 1, r = min(b - a + 1, d - c + 1), mid, ans = 0;
while (l <= r) {
mid = l + r >> 1;
if (check(mid, a, b, c)) ans = mid, l = mid + 1;
else r = mid - 1;
} cout << ans << "\n";
}
return 0;
}
|