LOJ3298 「BJOI2020」封印 题解

LOJ3298 「BJOI2020」封印

新鲜出炉的 2020 省选题嗷。

首先对于每个 $s$ 的后缀 $i$ 找到其与 $t$ 的最长公共子串长度 $f_i$，这个把 $s$ 和 $t$ 隔一个字符并起来做 SA，然后从前往后从后往前扫一遍即可。

对于每个询问，相当于求 $\max_{i=l}^r \min(f_i, r - i + 1)$。

注意到 $f_i \ge f_{i-1} - 1$，因此 $\min(f_i, r - i + 1)$ 取到 $r-i+1$ 的位置一定是一个后缀。

二分到决策交换点，然后求一个 RMQ 即可，时间复杂度 $\mathcal O(n \log n)$。

const int N = 4e5 + 7, inf = 1e9;
int n, m, q, f[N][21];
char s[N], t[N];

struct SA {
	char s[N];
	int n, m = 127, sa[N], rk[N<<1|1], tp[N<<1|1], tx[N], he[N];
	inline void sort() {
		for (int i = 1; i <= m; i++) tx[i] = 0;
		for (int i = 1; i <= n; i++) ++tx[rk[i]];
		for (int i = 1; i <= m; i++) tx[i] += tx[i-1];
		for (int i = n; i; i--) sa[tx[rk[tp[i]]]--] = tp[i]; 
	}
	inline bool pd(int i, int j, int k) {
		return tp[i] == tp[j] && tp[i+k] == tp[j+k];
	}
	inline void main() {
		for (int i = 1; i <= n; i++) rk[i] = s[i], tp[i] = i;
		sort();
		for (int k = 1, p = 0; p < n; k <<= 1, m = p) {
			p = 0;
			for (int i = 1; i <= k; i++) tp[++p] = n - k + i;
			for (int i = 1; i <= n; i++)
				if (sa[i] > k) tp[++p] = sa[i] - k;
			sort(), swap(rk, tp), rk[sa[1]] = p = 1;
			for (int i = 2; i <= n; i++)
				rk[sa[i]] = p += !pd(sa[i], sa[i-1], k); 
		}
		for (int i = 1, p = 0; i <= n; i++) {
			if (p) --p;
			int j = sa[rk[i]-1];
			while (s[i+p] == s[j+p]) ++p;
			he[rk[i]] = p;
		}
	}
} sa;

inline int ask(int l, int r) {
	if (l > r) return 0;
	int w = log2(r - l + 1);
	return max(f[l][w], f[r-(1<<w)+1][w]);
}

int main() {
	rds(s, n), rds(t, m);
	for (int i = 1; i <= n; i++) sa.s[i] = s[i];
	sa.s[n+1] = 1;
	for (int i = 1; i <= m; i++) sa.s[i+n+1] = t[i];
	sa.n = n + m + 1;
	sa.main();
	for (int i = 1, k = inf; i <= sa.n; i++) {
		k = min(k, sa.he[i]);
		if (sa.sa[i] <= n && k != inf) f[sa.sa[i]][0] = k;
		else k = inf;
	}
	for (int i = sa.n, k = inf; i; i--) {
		if (sa.sa[i] <= n && k != inf) f[sa.sa[i]][0] = max(f[sa.sa[i]][0], k);
		else k = inf;
		k = min(k, sa.he[i]);
	}
	int w = log2(n);
	for (int i = 0; i < w; i++)
		for (int l = 1; l + (1 << (i + 1)) - 1 <= n; l++)
			f[l][i+1] = max(f[l][i], f[l+(1<<i)][i]);
	rd(q);
	for (int i = 1, l, r; i <= q; i++) {
		rd(l, r);
		int L = l - 1, R = r;
		while (L < R) {
			int D = (L + R + 1) >> 1;
			if (f[D][0] < r - D + 1) L = D;
			else R = D - 1;
		}
		print(max(r - L, ask(l, L)));
	}
	return 0;
}