题目

求区间最长回文串长度

\(1 \le n\le 5 \times 10^5\)

题解

比较妙的做法，主要是在询问部分

预处理出以某位为中心回文半径长 \(p_i\)，马拉车和二分+哈希均可

然后考虑询问区间 \([l..r]\)

二分一个答案半径，\(\text st\) 表维护 \([l_{new}+mid-1,r_{new}-mid+1]\) 的 \(p\) 的最大值

于是就成了判定问题

\(Code\)

#include<cstdio>

#include<cstring>

#include<iostream>

using namespace std;

const int N = 5e5 + 5;

int n, q, p[N << 1], lg[N << 1], f[N << 1][22];

char s[N], str[N << 1];

inline void read(int &x)

{

	x = 0; int f = 1; char ch = getchar();

	while (ch < '0' || ch > '9') f = (ch == '-' ? -1 : f), ch = getchar();

	while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();

	x *= f;

}

inline void manacher()

{

	str[0] = '@', str[1] = '#', n = 2;

	int len = strlen(s);

	for(register int i = 0; i < len; i++) str[n++] = s[i], str[n++] = '#';

	str[n] = '\0';

	int mx = 0, id = 0;

	for(register int i = 1; i <= n; i++)

	{

		p[i] = (i < mx ? min(p[2 * id - i], mx - i) : 1);

		while (str[i + p[i]] == str[i - p[i]]) ++p[i];

		if (i + p[i] > mx) mx = i + p[i], id = i;

	}

}

inline int query(int i, int j)

{

	if (i > j) return 0;

	int k = lg[j - i + 1];

	return max(f[i][k], f[j - (1 << k) + 1][k]);

}

inline void st_table()

{

	for(register int i = 1; i <= n; i++) f[i][0] = p[i];

	for(register int i = 2; i <= n; i++) lg[i] = lg[i - 1] + ((1 << (lg[i - 1] + 1)) == i ? 1 : 0);

	for(register int j = 1; j <= lg[n]; j++)

		for(register int i = 1; i + (1 << j) - 1 <= n; i++)

			f[i][j] = max(f[i][j - 1], f[i + (1 << j - 1)][j - 1]);

}

int main()

{

	freopen("palindrome.in", "r", stdin);

	freopen("palindrome.out", "w", stdout);

	scanf("%s%d", s, &q);

	manacher(), st_table();

	for(int l, r; q; --q)

	{

		read(l), read(r), l = (l << 1) - 1, r = (r << 1) + 1;

		int ans = 1, L = 2, R = r - l + 1, mid;

		while (L <= R)

		{

			mid = (L + R) >> 1;

			if (query(l + mid - 1, r - mid + 1) >= mid) ans = mid, L = mid + 1;

			else R = mid - 1;

		}

		printf("%d\n", ans - 1);

	}

}

巴特西

JZOJ 2483. 【GDKOI 2021提高组DAY1】回文(palindrome)

题目

题解

\(Code\)

最新文章

热门文章