Description：

给一个字符串，多次询问 $s[a\sim b]$ 的所有子串和 $s[c\sim d]$ 的 $LCP$ 的最大值。

$1\leqslant n\leqslant 10^5$

Solution：

既然是 $LCP$ ，那就先把后缀数组求出来，然后每次询问先二分一个长度，然后问题就变成了和 $s[c\sim d]$ 的 $LCP\geqslant mid$ 的所有子串中是否有 $s[a\sim b]$ 的子串，这个可以在 $height$ 数组中二分出合法的左边界和右边界，问题就变成了查询这个区间中是否有在 $[a,b-mid+1]$ 之间的，这个用一个主席树求就可以了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

inline int rd()

{

	register int res = 0,f = 1;

	register char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 100010

char getc()

{

	register char c = getchar();

	while(!isalpha(c))c = getchar();

	return c;

}

char s[MAXN];

int sa[MAXN],rnk[MAXN],height[MAXN];

int t1[MAXN],t2[MAXN],c[MAXN];

inline void make_SA(int n,int m)

{

	register int *x = t1,*y = t2;

	register int p;

	for(register int i = 1;i <= m;++i)c[i] = 0;

	for(register int i = 1;i <= n;++i)++c[x[i] = s[i]];

	for(register int i = 1;i <= m;++i)c[i] += c[i - 1];

	for(register int i = n;i >= 1;--i)sa[c[x[i]]--] = i;

	for(register int k = 1;k <= n;k = k << 1)

	{

		p = 0;

		for(register int i = n - k + 1;i <= n;++i)y[++p] = i;

		for(register int i = 1;i <= n;++i)if(sa[i] > k)y[++p] = sa[i] - k;

		for(register int i = 1;i <= m;++i)c[i] = 0;

		for(register int i = 1;i <= n;++i)++c[x[y[i]]];

		for(register int i = 1;i <= m;++i)c[i] += c[i - 1];

		for(register int i = n;i >= 1;--i)sa[c[x[y[i]]]--] = y[i];

		p = 1;

		swap(x,y);x[sa[1]] = 1;

		for(register int i = 2;i <= n;++i)

		{

			x[sa[i]] = (y[sa[i]] == y[sa[i - 1]] && y[sa[i] + k] == y[sa[i - 1] + k] ? p : ++p);

		}

		if(p >= n)break;

		m = p;

	}

	for(register int i = 1;i <= n;++i)

	{

		rnk[sa[i]] = i;

	}

	register int k = 0;

	for(register int i = 1;i <= n;++i)

	{

		if(rnk[i] == 1)continue;

		if(k)--k;

		int j = sa[rnk[i] - 1];

		while(i + k <= n && s[i + k] == s[j + k])++k;

		height[rnk[i]] = k;

	}

	return;

}

struct node

{

	int lc,rc;

	int sum;

	node(){sum = 0;}

}t[MAXN * 30];

int ptr = 0;

inline int newnode(){return ++ptr;}

int root[MAXN];

void build(int &rt,int l,int r)

{

	rt = newnode();

	if(l == r)return;

	register int mid = ((l + r) >> 1);

	build(t[rt].lc,l,mid);

	build(t[rt].rc,mid + 1,r);

	return;

}

void insert(int &rt,int p,int l,int r)

{

	register int k = newnode();t[k] = t[rt];rt = k;

	++t[rt].sum;

	if(l == r)return;

	register int mid = ((l + r) >> 1);

	if(p <= mid)insert(t[rt].lc,p,l,mid);

	else insert(t[rt].rc,p,mid + 1,r);

	return;

}

int query(int rtr,int rtl,int L,int R,int l,int r)

{

	if(L <= l && r <= R)return t[rtr].sum - t[rtl].sum;

	register int res = 0;

	register int mid = ((l + r) >> 1);

	if(L <= mid)res += query(t[rtr].lc,t[rtl].lc,L,R,l,mid);

	if(R > mid)res += query(t[rtr].rc,t[rtl].rc,L,R,mid + 1,r);

	return res;

}

int f[MAXN][18];

int lg2[MAXN];

inline int calc(int l,int r)

{

	register int len = lg2[r - l + 1];

	return min(f[l][len],f[r - (1 << len) + 1][len]);

}

inline int getl(int p,int len)

{

	register int l = 1,r = p,mid;

	while(l < r)

	{

		mid = ((l + r) >> 1);

		if(calc(mid + 1,p) >= len)r = mid;

		else l = mid + 1;

	}

	return l;

}

inline int getr(int p,int len)

{

	register int l = p,r = n,mid;

	while(l < r)

	{

		mid = ((l + r + 1) >> 1);

		if(calc(p + 1,mid) >= len)l = mid;

		else r = mid - 1;

	}

	return l;

}

inline bool check(int len,int p,int l,int r)

{

	p = rnk[p];

	register int lef = getl(p,len),rig = getr(p,len);

	return query(root[rig],root[lef - 1],l,r - len + 1,1,n);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(register int i = 1;i <= n;++i)s[i] = getc();

	for(register int i = 2;i <= n;++i)lg2[i] = lg2[i >> 1] + 1;

	make_SA(n,256);

	build(root[0],1,n);

	for(register int i = 1;i <= n;++i)

	{

		root[i] = root[i - 1];

		insert(root[i],sa[i],1,n);

	}

	for(register int i = 1;i <= n;++i)f[i][0] = height[i];

	for(register int k = 1;k <= 17;++k)

		for(register int i = 1;i <= n - (1 << k) + 1;++i)

			f[i][k] = min(f[i][k - 1],f[i + (1 << (k - 1))][k - 1]);

	register int a,b,x,y;

	for(register int i = 1;i <= m;++i)

	{

		a = rd();b = rd();x = rd();y = rd();

		register int l = 0,r = min(b - a + 1,y - x + 1),mid;

		while(l < r)

		{

			mid = ((l + r + 1) >> 1);

			if(check(mid,x,a,b))l = mid;

			else r = mid - 1;

		}

		printf("%d\n",l);

	}

	return 0;

}