命題
有一个长为$n$的字符串$s$和$m$个詢問，每个詢問均有$a,b,c,d$四个参数，问子串$s[a\dots b]$的所有子串和$s[c\dots d]$的最长公
共前缀的长度的最大值是多少。
最長公共前綴暗示著應使用後綴數組，處理好相應的數組后暴力使用ST表匹配的複雜度為$O(n^2)$，無法解決問題。
這個問題最棘手的地方是存在的限制過多：因為是處理所有子串，即使使用後綴數組求出了$LCP$（最長公共前綴），還需要受多個字符串長度的限制才能得到最終答案。
所以不妨考慮先確定一個答案的長度來簡化問題，設該答案為$x$，則僅有$[a,b-x+1]$為可行的左端點。我們假設$x$是答案，把以$c$為左端點的後綴的排名分別向前、向後拓展，找到最長的一個區間$[l,r]$使得它們的$LCP\geq x$，這時如果$[a,b-x+1]$中的存在一個端點的後綴的排名出現在$[l,r]$之間，則可以確定真正的答案至少為$x$。
這時我們發現小於$x$的一定成立，大於$x$的在某一個值后就永遠不成立，由此可知答案具有單調性，所以直接二分答案。
可如何確定是否$[a,b-x+1]$中的存在一個端點的後綴的排名出現在$[l,r]$之間呢？對於區間我們需要一棵線段樹來維護在某一“時刻”原字符串的某一後綴是否出現，所以把後綴數組的各個元素看做時間軸，每一個時刻按後綴數組的次序添加相應後綴，可使用主席樹進行可持久化。
時間複雜度為$O(mlog^2n)$，空間複雜度為$O(nlogn)$。
注
一開始寫的程序TLE，十分不解，去LibreOJ下載數據測了一遍發現后幾個點跑3秒+，更加十分不解。偶然看到有人預處理了ST表查詢中$log$的答案，於是乎也改成了預處理，然後。。。奇跡發生了。
所以在此強烈聲明：複雜度集中的地方切記不要使用內置函數，請盡量自行實現或直接預處理。
（$pow$，$log2$哭暈在廁所。。。）
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <cctype>
#include <cmath>
template <typename _Tp>
void read(_Tp &a, char c = 0) {
for (c = getchar(); !isdigit(c); c = getchar());
for (a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar());
}
const int N = 1e5 + 5;
const int k = 21;
int n, m, sa[N], rk[N], ht[N];
char r[N];
namespace SPARSE_TABLE {
int st[N][21], Log[N];
void getST(int n, int *ht) {
for (int i = 2; i <= n; i++) Log[i] = Log[i >> 1] + 1;
memset(st, 127 / 3, sizeof st);
for (int i = 1; i <= n; i++) st[i][0] = ht[i];
for (int j = 1; j < 21; j++)
for (int i = 1; i + (1 << (j - 1)) <= n; i++)
st[i][j] = std :: min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
int getMin(int l, int r) {
int k = Log[r - l + 1];
return std :: min(st[l][k], st[r - (1 << k) + 1][k]);
}
}
namespace SUFFIX_ARRAY {
int buf1[N], buf2[N], buc[N];
void sort(char *s, int n, int *sa, int *rk, int *ht) {
int *x = buf1, *y = buf2, m = 26;
for (int i = 0; i <= m; i++) buc[i] = 0;
for (int i = 1; i <= n; i++) buc[x[i] = s[i] - 'a' + 1]++;
for (int i = 1; i <= m; i++) buc[i] += buc[i - 1];
for (int i = n; i; i--) sa[buc[x[i]]--] = i;
for (int k = 1; k <= n; k <<= 1) {
int p = 0;
for (int i = n - k + 1; i <= n; i++) y[++p] = i;
for (int i = 1; i <= n; i++) if (sa[i] > k) y[++p] = sa[i] - k;
for (int i = 0; i <= m; i++) buc[i] = 0;
for (int i = 1; i <= n; i++) buc[x[y[i]]]++;
for (int i = 1; i <= m; i++) buc[i] += buc[i - 1];
for (int i = n; i; i--) sa[buc[x[y[i]]]--] = y[i];
std :: swap(x, y), x[sa[1]] = p = 1;
for (int i = 2; i <= n; i++)
if (y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k]) x[sa[i]] = p;
else x[sa[i]] = ++p;
if ((m = p) >= n) break;
}
for (int i = 1; i <= n; i++) rk[sa[i]] = i;
for (int k = 0, j = 0, i = 1; i <= n; ht[rk[i++]] = k)
for (k ? k-- : 0, j = sa[rk[i] - 1]; s[i + k] == s[j + k]; k++);
}
}
namespace FUNC_SEGMENT_TREE {
int tot, rt[N];
struct node { int l, r, val; } tr[k * N];
void __add(int &x, int y, int l, int r, int p) {
x = ++tot;
(tr[x] = tr[y]).val++;
if (l == r) return;
int mid = (l + r) >> 1;
if (p <= mid) __add(tr[x].l, tr[y].l, l, mid, p);
else __add(tr[x].r, tr[y].r, mid + 1, r, p);
}
void add(int *sa, int n) { for (int i = 1; i <= n; i++) __add(rt[i], rt[i - 1], 1, n, sa[i]); }
int __ask(int x, int l, int r, int L, int R) {
if (!x) return 0;
if (L <= l && r <= R) return tr[x].val;
int ret = 0, mid = (l + r) >> 1;
if (L <= mid) ret += __ask(tr[x].l, l, mid, L, R);
if (R > mid) ret += __ask(tr[x].r, mid + 1, r, L, R);
return ret;
}
int ask(int l, int r, int a, int b, int n) { return __ask(rt[r], 1, n, a, b) - __ask(rt[l - 1], 1, n, a, b); }
}
namespace DEFAULT {
bool check(int x, int a, int b, int c, int d) {
int L, R, l, r, mid = 0;
L = rk[c], R = n + 1;
while (L + 1 < R) { mid = (L + R) >> 1; SPARSE_TABLE :: getMin(rk[c] + 1, mid) >= x ? L = mid : R = mid; }
r = L; L = 0, R = rk[c];
while (L + 1 < R) { mid = (L + R) >> 1; SPARSE_TABLE :: getMin(mid + 1, rk[c]) >= x ? R = mid : L = mid; }
l = R;
return FUNC_SEGMENT_TREE :: ask(l, r, a, b - x + 1, n);
}
}
int main() {
read(n), read(m);
scanf("%s", r + 1);
SUFFIX_ARRAY :: sort(r, n, sa, rk, ht);
SPARSE_TABLE :: getST(n, ht);
FUNC_SEGMENT_TREE :: add(sa, n);
register int a, b, c, d;
while (m--) {
read(a), read(b), read(c), read(d);
int L = 0, R = std :: min(d - c + 1, b - a + 1) + 1, mid = 0;
while (L + 1 < R) { mid = (L + R) >> 1; DEFAULT :: check(mid, a, b, c, d) ? L = mid : R = mid; }
printf("%d\n", L);
}
return 0;
}
Code language: PHP (php)