自动搬运

查看原文

来自洛谷，原作者为

	FChang 2025/8/23 AFOed

搬运于2025-08-24 23:17:16，当前版本为作者最后更新于2025-05-06 16:33:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

我的 std 做法很蠢。

你可以选择用高级的线段树合并做掉它，并且良心出题人没有强制在线。

再次感谢 sunset_breeze 给出的线段树合并解法，Vector 给出的非随机数据下的解法。

solution

对 $S$ 建出回文自动机，然后对于 $fail$ 树做倍增，在建出回文自动机时记录这个回文串第一次出现的位置。

将长度为 $len_2$ 的回文串存在一个 vector 中，根据 $fail$ 的定义，对于每一个长度为 $len_2$ 的回文串，倍增查找是否存在长度为 $len_1$ 的回文前缀，输出之前记录的最靠前的位置即可。

时间复杂度 $\mathcal{O}(n \times 15)$。

std

#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, q;
char a[N];
int len[N], fail[N], ch[N][27], cur, pos, tot = 1;
inline int getfail (int x, int i) {
	while (i - len[x] - 1 < 0 || a[i - len[x] - 1] != a[i]) x = fail[x];
	return x;
}
vector <int> e[N], lnk[N];
int f[N][21], dep[N], down[N];
inline void dfs (int x, int fa) {
	f[x][0] = fa, dep[x] = dep[fa] + 1;
	for (int i = 1; i <= 19; ++ i) f[x][i] = f[f[x][i - 1]][i - 1];
	for (auto v : e[x]) {
		if (v == fa) continue;
		dfs (v, x);
	}
	return ;
}
signed main () {
	ios::sync_with_stdio (0);
	cin.tie (0), cout.tie (0);
	cin >> n >> q;
	cin >> (a + 1);
	fail[0] = 1, len[1] = -1;
	e[0].push_back (1), e[1].push_back (0);
	for (int i = 1; i <= n; ++ i) {
		pos = getfail (cur, i);
		if (!ch[pos][a[i] - 'a']) {
			fail[++ tot] = ch[getfail (fail[pos], i)][a[i] - 'a'];
			e[fail[tot]].push_back (tot), e[tot].push_back (fail[tot]);
			ch[pos][a[i] - 'a'] = tot;
			len[tot] = len[pos] + 2;
			down[tot] = i - len[tot] + 1;
			lnk[len[tot]].push_back (tot);
		}
		cur = ch[pos][a[i] - 'a'];
	}
	dfs (1, 1);
	dfs (0, 0);
	for (int i = 1, l, r; i <= q; ++ i) {
		cin >> l >> r;
		int ans = n + 1;
		for (auto x : lnk[r]) {
			int val = down[x];
			for (int i = 19; i >= 0; -- i) if (len[f[x][i]] >= l) x = f[x][i];
			if (len[x] == l) {
				ans = min (ans, val);
				break;
			}
		}
		if (ans != n + 1) cout << ans << "\n";
		else cout << "-1\n";
	}
	return 0;
}