夏晓光(loveJY)的博客

做法:

二分答案,变成判定问题,相当于询问某个串的endpos有没有在$[l+len-1,r]$中出现,直接做即可

有许多的坑

比如定位的时候不能定位错了,是r-l+1

线段树合并要开新节点(这我直接抄没啥锅qwq)

但是数据结构题只要别写sb小错误都能调吧qwq

对对对!数组要照着2e5log开!!我一开始re了/ll

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 4e5 + 7;
int n, m;
char s[MAXN];

const int MAXT = 5e6 + 7;
namespace seg {
#define mid ((l+r)>>1)
	int tr[MAXT], ls[MAXT], rs[MAXT], tot, root[MAXN];
	inline void mdf(int &k, int l, int r, int p, int v) {
		if(!k)k = ++tot;
		if(l == r) {
			tr[k] += v;
			return ;
		}
		if(p <= mid)mdf(ls[k], l, mid, p, v);
		else mdf(rs[k], mid + 1, r, p, v);
		tr[k] = tr[ls[k]] + tr[rs[k]];
	}
	inline int merge(int x, int y) {
		if(!x || !y)return x | y;//公共节点,我们是不会更改的
		//而不公共的节点才可能更改,因为我们endpos只会增多
		int k = ++tot;
		ls[k] = merge(ls[x], ls[y]);
		rs[k] = merge(rs[x], rs[y]);
		tr[k] = tr[ls[k]] + tr[rs[k]];
		return k;
	}
	inline int qry(int k, int l, int r, int L, int R) {
		if(!k)return 0;
		if(L <= l && r <= R)
			return tr[k];
		if(R <= mid)return qry(ls[k], l, mid, L, R);
		else if(L > mid)return qry(rs[k], mid + 1, r, L, R);
		else return qry(ls[k], l, mid, L, R) + qry(rs[k], mid + 1, r, L, R);
	}
	inline void	outtree(int k, int l, int r) {
		if(ls[k])outtree(ls[k], l, mid);
		printf("%d %d %d \n", l, r, tr[k]);
		if(rs[k])outtree(rs[k], mid + 1, r);
		return;
	}
#undef mid
}

namespace sam {
	int ch[MAXN][26], fa[20][MAXN], T, lst, len[MAXN];
	int c[MAXN], a[MAXN];
	inline void ins(int e, int c) {
		int p = lst, q, nq;
		int np = lst = ++T;
		len[np] = len[p] + 1;
		seg::mdf(seg::root[np], 1, n, e, 1);
		for(; p && !ch[p][c]; p = fa[0][p])ch[p][c] = np;
		if(!p) {
			fa[0][np] = 1;
		} else {
			q = ch[p][c];
			if(len[q] == len[p] + 1) {
				fa[0][np] = q;
				return;
			}
			nq = ++T;
			len[nq] = len[p] + 1;
			fa[0][nq] = fa[0][q];
			memcpy(ch[nq], ch[q], sizeof(ch[q]));
			fa[0][np] = fa[0][q] = nq;
			for(; ch[p][c] == q; p = fa[0][p])ch[p][c] = nq;
		}
	}
	inline void init() {
		for(int i = 1; i <= 19; ++i)
			for(int j = 1; j <= T; ++j) {
				fa[i][j] = fa[i - 1][fa[i - 1][j]]; //跳就完了...
			}
		for(int i = 1; i <= T; ++i)
			++c[len[i]];
		for(int i = 1; i <= n; ++i)
			c[i] += c[i - 1];
		for(int i = 1; i <= T; ++i)
			a[c[len[i]]--] = i;
		for(int i = T; i; --i) {
			int u = a[i];
			seg::root[fa[0][u]] = seg::merge(seg::root[fa[0][u]], seg::root[u]);
		}
		return;
	}
}
using namespace sam;

int rc[MAXN];

inline int find(int l, int r) {
	int u = rc[r];
	for(int i = 19; i >= 0; --i) {
		if(len[fa[i][u]] >= r - l + 1) {
			u = fa[i][u];
		}
	}
	//跳完之后就是满足其父亲小于于,也就是这个点表示啦!
	return u;
}

inline int chk(int l, int r, int L, int R) {
	if(r - l > R - L)return 0;
	int u = find(l, r);
	return seg::qry(seg::root[u], 1, n, L + r - l, R);
}

int main() {
	scanf("%d%d", &n, &m);
	scanf("%s", s + 1);
	lst = T = 1;
	for(int i = 1; i <= n; ++i) {
		ins(i, s[i] - 'a');
		rc[i] = lst;
	}
	init();
	for(int i = 1, a, b, c, d; i <= m; ++i) {
		scanf("%d%d%d%d", &a, &b, &c, &d);
		int l = 1, r = d - c + 1, ans = 0;
		while(l <= r) {
			int mid = (l + r) >> 1;
			if(chk(c, c + mid - 1, a, b)) {
				ans = mid;
				l = mid + 1;
			} else {
				r = mid - 1;
			}
		}
		printf("%d\n", ans);
	}
	return 0;
}