144 lines
3.5 KiB
C++
144 lines
3.5 KiB
C++
#include <algorithm>
|
|
#include <cmath>
|
|
#include <cstdio>
|
|
#include <cstring>
|
|
#include <iostream>
|
|
#include <list>
|
|
#include <unordered_map>
|
|
using namespace std;
|
|
typedef long long LL;
|
|
typedef long double LDB;
|
|
const int kMaxN = 1e5 + 10;
|
|
struct state {
|
|
int len, link;
|
|
unordered_map<char, int> next;
|
|
};
|
|
int n, m;
|
|
char str[kMaxN];
|
|
state st[kMaxN * 2];
|
|
int sz, last;
|
|
int prefix_node_id[kMaxN];
|
|
int root_of_node[kMaxN * 2];
|
|
struct SegNodeType {
|
|
int lc, rc, sum;
|
|
};
|
|
SegNodeType seg[kMaxN * 60];
|
|
int seg_node_tot = 0;
|
|
list<int> G[kMaxN * 2];
|
|
int max_depth, fast_jump[kMaxN * 2][20];
|
|
void sam_init() {
|
|
st[0].len = 0;
|
|
st[0].link = -1;
|
|
sz++;
|
|
last = 0;
|
|
}
|
|
void sam_extend(char c) {
|
|
int cur = sz++;
|
|
st[cur].len = st[last].len + 1;
|
|
int p = last;
|
|
while (p != -1 && !st[p].next.count(c)) {
|
|
st[p].next[c] = cur;
|
|
p = st[p].link;
|
|
}
|
|
if (p == -1) {
|
|
st[cur].link = 0;
|
|
} else {
|
|
int q = st[p].next[c];
|
|
if (st[p].len + 1 == st[q].len) {
|
|
st[cur].link = q;
|
|
} else {
|
|
int clone = sz++;
|
|
st[clone].len = st[p].len + 1;
|
|
st[clone].next = st[q].next;
|
|
st[clone].link = st[q].link;
|
|
while (p != -1 && st[p].next[c] == q) {
|
|
st[p].next[c] = clone;
|
|
p = st[p].link;
|
|
}
|
|
st[q].link = st[cur].link = clone;
|
|
}
|
|
}
|
|
last = cur;
|
|
}
|
|
void InsertBasicEndPos(int &rt, int L, int R, int pos) {
|
|
if (rt == 0) rt = ++seg_node_tot;
|
|
seg[rt].sum++;
|
|
if (L == R) return;
|
|
int M = (L + R) >> 1;
|
|
if (pos <= M)
|
|
InsertBasicEndPos(seg[rt].lc, L, M, pos);
|
|
else
|
|
InsertBasicEndPos(seg[rt].rc, M + 1, R, pos);
|
|
}
|
|
int Query(int rt, int L, int R, int ql, int qr) {
|
|
if (ql <= L && R <= qr) return seg[rt].sum;
|
|
int M = (L + R) >> 1;
|
|
int res = 0;
|
|
if (ql <= M) res += Query(seg[rt].lc, L, M, ql, qr);
|
|
if (qr >= M + 1) res += Query(seg[rt].rc, M + 1, R, ql, qr);
|
|
return res;
|
|
}
|
|
int MergeSeg(int p, int q, int L, int R) {
|
|
if (p == 0 || q == 0) return p + q;
|
|
int cur = ++seg_node_tot;
|
|
seg[cur].sum = seg[p].sum + seg[q].sum;
|
|
if (L < R) {
|
|
int M = (L + R) >> 1;
|
|
seg[cur].lc = MergeSeg(seg[p].lc, seg[q].lc, L, M);
|
|
seg[cur].rc = MergeSeg(seg[p].rc, seg[q].rc, M + 1, R);
|
|
}
|
|
return cur;
|
|
}
|
|
void Dfs(int nd) {
|
|
for (int p = 1; p <= max_depth; p++) {
|
|
if (fast_jump[nd][p - 1] == -1)
|
|
fast_jump[nd][p] = -1;
|
|
else
|
|
fast_jump[nd][p] = fast_jump[fast_jump[nd][p - 1]][p - 1];
|
|
}
|
|
for (auto v : G[nd]) {
|
|
fast_jump[v][0] = nd;
|
|
Dfs(v);
|
|
root_of_node[nd] = MergeSeg(root_of_node[nd], root_of_node[v], 1, n);
|
|
}
|
|
}
|
|
bool IsValid(int len, int a, int b, int c, int d) {
|
|
int cur = prefix_node_id[c + len - 1];
|
|
for (int p = max_depth; p >= 0; p--) {
|
|
if (fast_jump[cur][p] != -1 && st[fast_jump[cur][p]].len >= len)
|
|
cur = fast_jump[cur][p];
|
|
}
|
|
return Query(root_of_node[cur], 1, n, a + len - 1, b) > 0;
|
|
}
|
|
int main() {
|
|
#ifdef local
|
|
freopen("pro.in", "r", stdin);
|
|
#endif
|
|
scanf("%d%d", &n, &m);
|
|
scanf("%s", str + 1);
|
|
sam_init();
|
|
for (int i = 1; i <= n; i++) {
|
|
sam_extend(str[i]);
|
|
prefix_node_id[i] = last;
|
|
InsertBasicEndPos(root_of_node[last], 1, n, i);
|
|
}
|
|
for (int i = 1; i < sz; i++) G[st[i].link].push_back(i);
|
|
max_depth = log2(sz + 1) + 1;
|
|
memset(fast_jump, -1, sizeof(fast_jump));
|
|
Dfs(0);
|
|
while (m-- > 0) {
|
|
int a, b, c, d;
|
|
scanf("%d%d%d%d", &a, &b, &c, &d);
|
|
int L = 0, R = min(b - a + 1, d - c + 1), M, res = 0;
|
|
while (L <= R) {
|
|
M = (L + R) >> 1;
|
|
if (IsValid(M, a, b, c, d)) {
|
|
res = M;
|
|
L = M + 1;
|
|
} else
|
|
R = M - 1;
|
|
}
|
|
printf("%d\n", res);
|
|
}
|
|
return 0;
|
|
} |