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
| #include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
const int N = 2E5 + 100;
int tr[N][26], len[N] = {-1}, fa[N], sz = 2, last = 1, pos[N], rpos[N];
void ins(int ch, int pp) {
int p = last, np = last = sz++; pos[np] = pp; rpos[pp] = np;
len[np] = len[p] + 1;
for (; p && !tr[p][ch]; p = fa[p]) tr[p][ch] = np;
if (!p) { fa[np] = 1; return; }
int q = tr[p][ch];
if (len[p] + 1 == len[q]) fa[np] = q;
else {
int nq = sz++; len[nq] = len[p] + 1;
memcpy(tr[nq], tr[q], sizeof tr[0]);
fa[nq] = fa[q]; fa[np] = fa[q] = nq;
for (; tr[p][ch] == q; p = fa[p]) tr[p][ch] = nq;
}
}
vector<int> G[N];
const int SP = 19;
int in[N], out[N], clk, pa[N][SP], ridx[N];
void dfs(int u, int fa) {
in[u] = ++clk; pa[u][0] = fa; ridx[clk] = u;
FOR (i, 1, SP) pa[u][i] = pa[pa[u][i - 1]][i - 1];
for (int& v: G[u]) dfs(v, u);
out[u] = clk;
}
int get_state(int l, int r) {
int u = rpos[l], s = r - l + 1;
FORD (i, SP - 1, -1) if (len[pa[u][i]] >= s) u = pa[u][i];
return u;
}
namespace tree {
#define lson l, l + (r - l) / 2
#define rson l + (r - l) / 2 + 1, r
struct P { int w, ls, rs; };
P a[N * 20];
int sz = 1;
int _new(int w, int ls, int rs) { a[sz] = {w, ls, rs}; return sz++; }
int ins(int o, int p, int v, int l, int r) {
if (l > p || p > r) return o;
if (l == r) return _new(a[o].w + v, 0, 0);
return _new(a[o].w + v, ins(a[o].ls, p, v, lson), ins(a[o].rs, p, v, rson));
}
bool query(int lo, int ro, int ql, int qr, int l, int r) {
if (lo + ro == 0 || l > qr || ql > r) return false;
if (ql <= l && r <= qr) return a[ro].w - a[lo].w > 0;
return query(a[lo].ls, a[ro].ls, ql, qr, lson) ||
query(a[lo].rs, a[ro].rs, ql, qr, rson);
}
}
char s[N];
int rt[N];
int main() {
#ifdef zerol
freopen("in", "r", stdin);
#endif
memset(pos, -1, sizeof pos);
int n, Qn; cin >> n >> Qn;
scanf("%s", s);
FORD (i, n - 1, -1) ins(s[i] - 'a', i);
FOR (i, 2, sz) G[fa[i]].push_back(i);
dfs(1, 1);
FOR (i, 1, clk + 1)
rt[i] = pos[ridx[i]] == -1 ? rt[i - 1] : tree::ins(rt[i - 1], pos[ridx[i]], 1, 0, n - 1);
while (Qn--) {
int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d); --a; --b; --c; --d;
int l = 1, r = d - c + 1, ans = 0;
while (l <= r) {
int m = (l + r) / 2;
int state = get_state(c, c + m - 1);
if (tree::query(rt[in[state] - 1], rt[out[state]], a, b - m + 1, 0, n - 1)) {
ans = m; l = m + 1;
} else r = m - 1;
}
printf("%d\n", ans);
}
}
|