其实是个套路题（？
首先，LCP 这种东西，不能直接求就优先考虑二分答案。
设二分出来的东西为 \(\newcommand\mid{\mathrm{mid}}\mid\)，那么就是相当于在整个字符串里，至少有一个以 \(s\) 为起点的后缀，使得
- \(s \in [a,b - \mid + 1]\)；
- 该后缀与以 \(c\) 为起点的后缀的 LCP 长度不小于 \(\mid\)。
注意到一个端点固定，另一个端点朝一方变化的区间最小值函数是单调的。
也即满足第二个条件的 \(s\) 应当属于后缀排名上包含 \(c\) 的一个区间。
这个可以二分出来。
然后用主席树维护一下二维偏序就 OK 了。
代码： 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
using namespace std;
const int N = 1e5;
const int LG = 17;
int n,m,lg2[N + 5];
char a[N + 5];
int sa[N + 5],rk[(N << 1) + 5],tpr[(N << 1) + 5],c[N + 5],height[N + 5];
int st[N + 5][LG + 5];
int l,r,mid,ans;
void build_SA()
{
static int m = 127;
memset(c,0,sizeof c);
for(register int i = 1;i <= n;++i)
++c[rk[i] = a[i]];
for(register int i = 1;i <= m;++i)
c[i] += c[i - 1];
for(register int i = n;i;--i)
sa[c[rk[i]]--] = i;
for(register int w = 1,p = 0;p < n;w <<= 1,m = p)
{
p = 0;
for(register int i = 1;i <= w;++i)
tpr[++p] = n - w + i;
for(register int i = 1;i <= n;++i)
if(sa[i] > w)
tpr[++p] = sa[i] - w;
memset(c,0,sizeof c);
for(register int i = 1;i <= n;++i)
++c[rk[i]];
for(register int i = 1;i <= m;++i)
c[i] += c[i - 1];
for(register int i = n;i;--i)
sa[c[rk[tpr[i]]]--] = tpr[i];
swap(rk,tpr),rk[sa[1]] = p = 1;
for(register int i = 2;i <= n;++i)
rk[sa[i]] = tpr[sa[i]] == tpr[sa[i - 1]] && tpr[sa[i] + w] == tpr[sa[i - 1] + w] ? p : ++p;
}
for(register int i = 1,k = 0;i <= n;++i)
{
k -= (bool)k;
for(;a[i + k] == a[sa[rk[i] - 1] + k];++k);
height[rk[i]] = k;
}
}
int query(int l,int r)
{
++l;
int lg = lg2[r - l + 1];
return min(st[l][lg],st[r - (1 << lg) + 1][lg]);
}
struct node
{
int sum;
int ls,rs;
} seg[(N << 5) + 10];
int rt[N + 5];
void insert(int x,int &p,int tl,int tr)
{
static int tot = 0;
seg[++tot] = seg[p],++seg[p = tot].sum;
if(tl == tr)
return ;
int mid = tl + tr >> 1;
x <= mid ? insert(x,seg[p].ls,tl,mid) : insert(x,seg[p].rs,mid + 1,tr);
}
int query(int l,int r,int p,int q,int tl,int tr)
{
if(l <= tl && tr <= r)
return seg[q].sum - seg[p].sum;
int mid = tl + tr >> 1;
int ret = 0;
l <= mid && (ret += query(l,r,seg[p].ls,seg[q].ls,tl,mid));
r > mid && (ret += query(l,r,seg[p].rs,seg[q].rs,mid + 1,tr));
return ret;
}
int check(int a,int b,int c,int x)
{
int l = 1,r = rk[c] - 1,mid,L = rk[c],R = rk[c];
while(l <= r)
mid = l + r >> 1,query(mid,rk[c]) >= x ? (r = mid - 1,L = mid) : (l = mid + 1);
l = rk[c] + 1,r = n;
while(l <= r)
mid = l + r >> 1,query(rk[c],mid) >= x ? (l = mid + 1,R = mid) : (r = mid - 1);
return query(L,R,rt[a - 1],rt[b - x + 1],1,n);
}
int main()
{
scanf("%d%d%s",&n,&m,a + 1);
for(register int i = 2;i <= n;++i)
lg2[i] = lg2[i >> 1] + 1;
build_SA();
for(register int i = 1;i <= n;++i)
st[i][0] = height[i];
for(register int i = 1;i <= LG;++i)
for(register int j = 1;j + (1 << i) - 1 <= n;++j)
st[j][i] = min(st[j][i - 1],st[j + (1 << i - 1)][i - 1]);
for(register int i = 1;i <= n;++i)
insert(rk[i],rt[i] = rt[i - 1],1,n);
for(int a,b,c,d;m;--m)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
l = 0,r = min(b - a + 1,d - c + 1);
while(l <= r)
mid = l + r >> 1,check(a,b,c,mid) ? (l = mid + 1,ans = mid) : (r = mid - 1);
printf("%d\n",ans);
}
}