C++ 解法, 执行用时: 421ms, 内存消耗: 44684K, 提交时间: 2021-06-06 14:42:34

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 500005;
int n, m;
char s[maxn];
#define ull unsigned long long
const int seed = 19491001;
ull hs[maxn], pw[maxn];
inline ull get(int l, int r) {
	return hs[r] - hs[l - 1] * pw[r - l + 1];
}
int getlcs(int i, int j) {
	int l = 1, r = min(i, j), res = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(get(i - mid + 1, i) == get(j - mid + 1, j))
			res = mid, l = mid + 1;
		else
			r = mid - 1;
	}
	return res;
}
int getlcp(int i, int j) {
	int l = 1, r = n - max(i, j) + 1, res = 0;
	while(l <= r) {
		int mid = (l + r) >> 1;
		if(get(i, i + mid - 1) == get(j, j + mid - 1))
			res = mid, l = mid + 1;
		else
			r = mid - 1;
	}
	return res;
}
bool cmp(int l1, int r1, int l2, int r2) {
	int len = getlcp(l1, l2);
	if(len >= min(r1 - l1 + 1, r2 - l2 + 1))
		return r1 - l1 < r2 - l2;
	return s[l1 + len] < s[l2 + len];
}
void init_hs() {
	pw[0] = 1;
	for(int i = 1; i <= n; i++) {
		pw[i] = pw[i - 1] * seed;
		hs[i] = hs[i - 1] * seed + s[i];
	}
}
int rt[maxn];
void lyndon() {
	static int st[maxn], top;
	top = 0;
	for(int i = n; i >= 1; i--) {
		st[++top] = i;
		while(top > 1 && cmp(i, st[top], st[top] + 1, st[top - 1]))
			top--;
		rt[i] = st[top];
	}
}
int len[maxn];
vector<int> ins[maxn];
vector<int> del[maxn];
void modify(int l, int r, int p) {
	ins[l].push_back(p);
	del[r + 1].push_back(p);
}
void find_runs() {
	for(int i = 1; i <= n; i++) {
		int p = rt[i] - i + 1;
		int L = i - getlcs(i - 1, rt[i]), R = rt[i] + getlcp(i, rt[i] + 1);
		if(R - L + 1 >= p * 2) 
			modify(L, R - p * 2 + 1, p);
	}
}
void init_runs() {
	init_hs();
	lyndon();
	find_runs();
	for(int i = 1; i <= n; i++)
		s[i] = 'a' + (25 - (s[i] - 'a'));
	lyndon();
	find_runs();
	for(int i = 1; i <= n; i++)
		s[i] = 'a' + (25 - (s[i] - 'a'));
}
int ans[maxn];
int main() {
	scanf("%s%d", s + 1, &m);
	n = strlen(s + 1);
	init_runs();
	
	multiset<int> s;
	for(int i = 1; i <= n; i++) {
		for(auto u : ins[i])
			s.insert(u);
		for(auto u : del[i])
			s.erase(s.find(u));
		if(s.size())
			len[i] = *s.begin();
	}
	
	for(int i = 1; i <= n; i++) {
		ans[i] = ans[i - 1];
		if(len[i] && (!ans[i] || cmp(i, i + len[i] * 2 - 1, ans[i], ans[i] + len[ans[i]] * 2 - 1)))
			ans[i] = i;
	}
	for(int i = 1, x; i <= m; i++) {
		scanf("%d", &x);
		if(ans[x])
			printf("%d %d\n", ans[x], ans[x] + len[ans[x]] * 2 - 1);
		else
			puts("-1");
	}
	return 0;
}