题目链接
题意：给定一个字符串(s)，有(m)次询问，每次指定两个区间([a..b])和([c..d])，求第一个区间的子串和第二个区间的(lcp)的最大值。
考虑二分答案(mid)，问题变为判定是否存在以([a+mid-1..b])结尾的长度为(mid)的串，与(s[c..c+mid-1])相等。
这里使用后缀自动机
建出(SAM)，找到(c+mid-1)在后缀自动机对应的节点，倍增找出包含长度(mid)的祖先，在它的(right)集合里查询是否存在([a+mid-1..b])中的位置。用线段树合并实现
复杂度(O(n log^2 n))
（倍增把小的一维放后面，速度快了(2)倍
#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>
using namespace std;
#define ll long long
inline char read() {
static const int IN_LEN = 1000000;
static char buf[IN_LEN], *s, *t;
return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
static bool iosig;
static char c;
for (iosig = false, c = read(); !isdigit(c); c = read()) {
if (c == '-') iosig = true;
if (c == -1) return;
}
for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
if (iosig) x = -x;
}
const int OUT_LEN = 10000000;
char obuf[OUT_LEN], *ooh = obuf;
inline void print(char c) {
if (ooh == obuf + OUT_LEN) fwrite(obuf, 1, OUT_LEN, stdout), ooh = obuf;
*ooh++ = c;
}
template<class T>
inline void print(T x) {
static int buf[30], cnt;
if (x == 0) print('0');
else {
if (x < 0) print('-'), x = -x;
for (cnt = 0; x; x /= 10) buf[++cnt] = x % 10 + 48;
while (cnt) print((char)buf[cnt--]);
}
}
inline void flush() { fwrite(obuf, 1, ooh - obuf, stdout); }
const int N = 100005, M = 19;
int n, m, lim, cnt, cnt2, last, pos[N], b[N], a[N<<1], root[N<<1], fa[N<<1], len[N<<1], lson[N*M*2], rson[N*M*2], f[N<<1][M], ch[N<<1][26];
char str[N];
bool s[N*M*2];
void modify(int l, int r, int &t, int pos){
s[t?t:t=++cnt2]=1;
if(l==r) return;
int mid=l+r>>1;
if(pos<=mid) modify(l, mid, lson[t], pos); else modify(mid+1, r, rson[t], pos);
}
int Merge(int x, int y){
if(!x || !y) return x|y;
int tmp=++cnt2;
s[tmp]=s[x]||s[y], lson[tmp]=Merge(lson[x], lson[y]), rson[tmp]=Merge(rson[x], rson[y]);
return tmp;
}
bool query(int l, int r, int t, int L, int R){
if(!t || L<=l && r<=R) return s[t];
int mid=l+r>>1;
if(R<=mid) return query(l, mid, lson[t], L, R);
else if(L>mid) return query(mid+1, r, rson[t], L, R);
else return query(l, mid, lson[t], L, R)||query(mid+1, r, rson[t], L, R);
}
inline void extend(int c){
int p=last, np=++cnt;
last=cnt, len[np]=len[p]+1;
while(p && !ch[p][c]) ch[p][c]=np, p=fa[p];
if(!p) fa[np]=1;
else{
int q=ch[p][c];
if(len[q]==len[p]+1) fa[np]=q;
else{
int nq=++cnt;
len[nq]=len[p]+1, memcpy(ch[nq], ch[q], sizeof ch[0]);
fa[nq]=fa[q], fa[q]=fa[np]=nq;
while(ch[p][c]==q) ch[p][c]=nq, p=fa[p];
}
}
modify(1, n, root[np], len[np]);
pos[len[np]]=np;
}
inline bool check(int l, int r, int p, int x){
p=pos[p];
for(int i=lim; ~i; --i) if(len[f[p][i]]>=x) p=f[p][i];
return query(1, n, root[p], l, r);
}
int main() {
read(n), read(m);
cnt=last=1;
char tmp;
while(isspace(tmp=read()));
extend(tmp-'a');
for(int i=2; i<=n; ++i) extend(read()-'a');
for(lim=1; 2<<lim<n; ++lim);
for(int i=1; i<=cnt; ++i) ++b[len[i]], f[i][0]=fa[i];
for(int i=1; i<=n; ++i) b[i]+=b[i-1];
for(int i=cnt; i; --i) a[b[len[i]]--]=i;
for(int i=cnt; i; --i) root[fa[a[i]]]=Merge(root[fa[a[i]]], root[a[i]]);
for(int i=1; i<=lim; ++i) for(int j=1; j<=cnt; ++j) f[j][i]=f[f[j][i-1]][i-1];
while(m--){
static int a, b, c, d;
read(a), read(b), read(c), read(d);
int l=1, r=min(b-a+1, d-c+1), ans=0;
while(l<=r){
int mid=l+r>>1;
if(check(a+mid-1, b, c+mid-1, mid)) ans=mid, l=mid+1; else r=mid-1;
}
print(ans), print('
');
}
return flush(), 0;
}