\(\text{[BZOJ3230] 相似子串 题解}\)

巧妙地利用了后缀数组的一些奇妙性质。

先考虑第一问。首先去处理本质不同的子串这个东西。这个东西我们显然是见过的，于是套路地建出 SA 求出 \(\operatorname{height}\) 数组。每一个子串对应的都是一个后缀的前缀。由于串都是本质不同的，那么两个串 \((l_1,r_1),(l_2,r_2)\) 的 \(\operatorname{lcp}\) 也就是 \(\operatorname{lcp(s_{l_1},s_{l_2})}\)，其中 \(\operatorname{s_i}\) 表示的是 \(s(i\sim n)\)。这样便是容易求的。

于是现在我们需要知道每个本质不同的串的编号和字符串内下标的对应关系。然后发现题目让我们给这些串排序。那么求出后缀数组的过程实际上也就给每个后缀排了序，而且容易发现的是对于后缀 \(s(i)\) 的每个前缀，他们在排序后的下标同样是连续的。这样我们可以求出每个子串的下标，但是需要留意的是我们要去重。那这个显然是容易的，对于 \(i\) 到 \(i+1\) 的转移，减去 \(\operatorname{height}_{i+1}\) 即可。

这样一来容易知道的是每个后缀的第一个前缀的排名，于是第一问可以二分去做。对于第二问，由于此时我们已经知道了串的左端点，那么右端点同样是容易得出的。于是反着建 SA 跑一遍即可。

注意开 long long。

代码：

#include <bits/stdc++.h>
#define N 200005
#define M 21
#define ll long long
using namespace std;
int n, q;
struct _SA {
	string s;
	int sa[N], rk[N], lk[N], id[N], cnt[N];
	void SA() {
		int m = 128, p = 0;
		for (int i = 1; i <= n; i++) cnt[rk[i] = s[i]]++;
		for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
		for (int i = n; i >= 1; i--) sa[cnt[rk[i]]--] = i;
		for (int w = 1;; w <<= 1, m = p) {
			int cur = 0;
			for (int i = n - w + 1; i <= n; i++) id[++cur] = i;
			for (int i = 1; i <= n; i++)
				if (sa[i] > w) id[++cur] = sa[i] - w;
			for (int i = 1; i <= m; i++) cnt[i] = 0;
			for (int i = 1; i <= n; i++) cnt[rk[i]]++;
			for (int i = 1; i <= m; i++) cnt[i] += cnt[i - 1];
			for (int i = n; i >= 1; i--) sa[cnt[rk[id[i]]]--] = id[i];
			swap(lk, rk);
			p = 0;
			for (int i = 1; i <= n; i++) {
				if (lk[sa[i]] == lk[sa[i - 1]] && lk[sa[i] + w] == lk[sa[i - 1] + w]) rk[sa[i]] = p;
				else rk[sa[i]] = ++p;
			}
			if (p == n) break;
		}
	}
	int h[N];
	void H() {
		for (int i = 1, k = 0; i <= n; i++) {
			if (k) --k;
			while (s[i + k] == s[sa[rk[i] - 1] + k]) ++k;
			h[rk[i]] = k;
		}
	}
	int st[N][M];
	void init() {
		SA();
		H();
		for (int i = 1; i <= n; i++) st[i][0] = h[i];
		for (int j = 1; j < M; j++)
			for (int i = 1; i <= n - (1 << j) + 1; i++)
				st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
	}
	int query(int l, int r) {
		int k = log2(r - l + 1);
		return min(st[l][k], st[r - (1 << k) + 1][k]);
	}
} a, b;
ll srt[N], ed[N];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	cin >> a.s;
	b.s = a.s;
	reverse(b.s.begin(), b.s.end());
	a.s = " " + a.s, b.s = " " + b.s;
	a.init(), b.init();
	srt[1] = 1, ed[1] = n - a.sa[1] + 1;
	for (int i = 2; i <= n; i++) 
		srt[i] = ed[i - 1] + 1, ed[i] = srt[i] + n - a.sa[i] - a.h[i];
	srt[n + 1] = 1e9;
	ll mx = ed[n];
	while (q--) {
		ll x, y;
		cin >> x >> y;
		if (y > mx)  {
			cout << "-1\n";
			continue;
		}
		int s1 = upper_bound(srt + 1, srt + n + 2, x) - srt - 1, s2 = upper_bound(srt + 1, srt + n + 2, y) - srt - 1;
		int l1 = a.sa[s1], l2 = a.sa[s2];
		int r1 = l1 + x - srt[s1] + a.h[s1], r2 = l2 + y - srt[s2] + a.h[s2];
		int A = 0, B = 0;
		if (s1 > s2) swap(s1, s2);
		if (s1 == s2) A = min(r1 - l1 + 1, r2 - l2 + 1);
		else A = a.query(s1 + 1, s2);
		s1 = b.rk[n - r1 + 1], s2 = b.rk[n - r2 + 1];
		if (s1 > s2) swap(s1, s2);
		if (s1 == s2) B = min(r1 - l1 + 1, r2 - l2 + 1);
		else B = b.query(s1 + 1, s2);
		A = min({A, r1 - l1 + 1, r2 - l2 + 1}), B = min({B, r1 - l1 + 1, r2 - l2 + 1});
		cout << (long long)A * A + (long long)B * B << '\n';
	}
	return 0;
}