题意： 给定字符串 $s$。总共 m 个询问，每次给定 $a, b, c, d$，问你子串 $s[a..b]$ 的所有子串和 $s[c..d]$ 的最长公共前缀的长度的最大值是多少。 $1\le n,m\le 100,000$，$a\le b$，$c\le d$，$1\le a,b,c,d\le n$。

很有意思的一道题。 首先，看到字符串的题就可以先盲猜二分。显然这道题的答案有单调性。

对于 check 函数，假设我们在判断 $m$ 是否可行。我们需要判断是否有 $x$ 满足：

1. $x \in [a, b - m + 1] \cap \text{Z}$
2. $lcp(x, c) \ge m$ 我们先考虑第二个限制。根据 height 的性质，两个位置的 $lcp$ 是他们之间 $height$ 的最小值。所以我们可以发现 $lcp(x,c)$ 关于 $rank_x$ 是单峰的，峰值在 $rank_c$ 取到。所以我们可以发现满足第二个限制的 $rank$ 构成一个连续的区间。我们可以二分求出这个区间。设这个区间为 $[l,r]$。 那么，这两个限制就相当于二位数点。我们用主席树来求答案。主席树上的每个点维护区间最大值。我们从小到打枚举原字符串的每个位置，将其对应的 $rank$ 的位置的值设为下标。然后我们判断第 $b - m + 1$ 号根中 $[l,r]$ 的最大值与 $a$ 的关系。如果 a 较小则可以，否则不行。 总复杂度：$O(n \log n + m \log^2 n)$