题意

给定一个长为 $n$ 的字符串 $s$ 和 $m$ 个问题，每个问题均有 $a,b,c,d$ 四个参数，求子串 $s[a..b]$ 的所有子串和 $s[c..d]$ 的最长公共前缀的长度的最大值是多少。

$1\le n,m\le 100,000$ 。

题解

SAM 例题。直接算长度太难，考虑二分长度：若二分到长度为 $\mathrm{len}$ ，接着查询子串 $s[a..b]$ 是否有子串等于 $s[c..(c+\mathrm{len}-1)]$ 即可。在 Parent Tree 上从 $s[1..(c+\mathrm{len}-1)]$ 所在结点倍增到最后一个最大长度大于等于 $\mathrm{len}$ 的节点，由于 SAM 的性质可以保证它一定是 $s[c..(c+\mathrm{len}-1)]$ 所在结点，判断它的结尾集合是否包含 $[a+\mathrm{len}-1,b]$ 的某个数就可以了。至于维护结尾集合，可以用权值线段树合并。

代码

const int N = 1e5 + 10;

inline ll Read() {
	ll x = 0, f = 1;
	char c = getchar();
	while (c != '-' && (c < '0' || c > '9')) c = getchar();
	if (c == '-') f = -f, c = getchar();
	while (c >= '0' && c <= '9') x = (x << 3) + (x << 1) + c - '0', c = getchar();
	return x * f;
}

namespace Main {

	int n, m;
	char s[N];

	namespace SAM {
		int Last, tot;
		int trans[N][26];
		int fail[N], maxlen[N];

		void Build () { Last = tot = 1; }
		void Insert (int c) {
			int p = Last, np = ++tot;
			maxlen[np] = maxlen[p] + 1;
			for (; p && !trans[p][c]; p = fail[p]) trans[p][c] = np;
			if (!p) fail[np] = 1;
			else {
				int q = trans[p][c];
				if (maxlen[q] == maxlen[p] + 1) fail[np] = q;
				else {
					int nq = ++tot; fail[nq] = fail[q];
					memcpy (trans[nq], trans[q], 26 << 2);
					maxlen[nq] = maxlen[p] + 1;
					for (; p && trans[p][c] == q; p = fail[p])
						trans[p][c] = nq;
					fail[np] = fail[q] = nq;
				}
			}
			Last = np;
		}
	}

	struct SegmentTree{
		struct Tree {
			int l, r, val;
		}t[N << 4];
		int tot;
		void Insert (int &p, int l, int r, int pos) {
			if (!p) p = ++tot;
			t[p].val ++;
			if (l == r) return ;
			int mid = l + r >> 1;
			if (pos <= mid) Insert (t[p].l, l, mid, pos);
			else Insert (t[p].r, mid + 1, r, pos);
		}
		int Query (int p, int l, int r, int L, int R) {
			if (L <= l && r <= R) return t[p].val;
			int mid = l + r >> 1; int ans = 0;
			if (L <= mid) ans += Query (t[p].l, l, mid, L, R);
			if (mid < R) ans += Query (t[p].r, mid + 1, r, L, R);
			return ans;
		}
		int Merge(int p, int q, int l, int r) {
			if (!p || !q) return p + q;
			int x = ++tot, mid = l + r >> 1;
			t[x].val = t[p].val + t[q].val;
			if (l == r) return x;
			t[x].l = Merge(t[p].l, t[q].l, l, mid);
			t[x].r = Merge(t[p].r, t[q].r, mid + 1, r);
			return x;
		}
	}st;

	int id[N], root[N], fa[N][25], t;
	int head[N], tot;
	struct edge {
		int to, nxt;
	}e[N];
	void Add(int u, int v) {
		e[++tot] = (edge) {v, head[u]}, head[u] = tot;
	}

	void dfs (int u) {
		for (int i = head[u]; i; i = e[i].nxt) {
			int v = e[i].to;
			fa[v][0] = u;
			dfs (v);
			root[u] = st.Merge(root[u], root[v], 1, n);
		}
	}

	bool check(int mid, int a, int b, int c, int d) {
		int now = id[c + mid - 1];
		for (int i = t; ~i; i--) if (fa[now][i] && SAM::maxlen[fa[now][i]] >= mid) now = fa[now][i];
		return st.Query(root[now], 1, n, a + mid - 1, b) > 0;
	}

	int main() {
		n = Read(), m = Read();
		scanf ("%s", s + 1);
		id[0] = 1;
		SAM::Build();
		for (int i = 1; i <= n; i++) {
			SAM::Insert(s[i] - 'a');
			id[i] = SAM::Last;
			st.Insert(root[SAM::Last], 1, n, i);
		}
		for (int i = 2; i <= SAM::tot; i++) Add(SAM::fail[i], i);
		t = log2(SAM::tot) + 1; dfs(1);
		for (int j = 1; j <= t; j++)
			for (int i = 1; i <= SAM::tot; i++)
				fa[i][j] = fa[fa[i][j-1]][j-1];
		for (int i = 1; i <= m; i++) {
			int a = Read(), b = Read(), c = Read(), d = Read();
			int l = 0, r = min (b - a + 1, d - c + 1), ans = 0;
			while (l <= r) {
				int mid = l + r >> 1;
				if (check(mid, a, b, c, d)) ans = mid, l = mid + 1;
				else r = mid - 1;
			}
			printf ("%d\n", ans);
		}
		return 0;
	}
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	return Main::main();
}