0%

【题解】HackerRank-Circular Palindromes

题目

https://www.hackerrank.com/challenges/circular-palindromes/problem

题意

求一个字符串的所有旋转的最长回文子串长度。

题解

  • 字符串复制一遍,manacher 预处理每个中心的最长回文串。
  • 对于每个区间 [L, R],考虑二分答案。如果存在长度为 m 的回文子串,在以 [L + m - 1, R - m + 1] (插入过间隔字符的区间)为中心的最长回文串要不小于 m。用 ST 表预处理区间最大值即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
#define FOR(i, x, y) for (decay<decltype(y)>::type i = (x), _##i = (y); i < _##i; ++i)
#define FORD(i, x, y) for (decay<decltype(x)>::type i = (x), _##i = (y); i > _##i; --i)
#ifdef zerol
#define dbg(args...) do { cout << "\033[32;1m" << #args << " -> "; err(args); } while (0)
#else
#define dbg(...)
#endif
void err() { cout << "\033[39;0m" << endl; }
template<template<typename...> class T, typename t, typename... Args>
void err(T<t> a, Args... args) { for (auto x: a) cout << x << ' '; err(args...); }
template<typename T, typename... Args>
void err(T a, Args... args) { cout << a << ' '; err(args...); }
// -----------------------------------------------------------------------------
const int N = 5E5 * 4 + 100;

int RL[N];
void manacher(int* a, int n) { // "abc" => "#a#b#a#"
int r = 0, p = 0;
FOR (i, 0, n) {
if (i < r) RL[i] = min(RL[2 * p - i], r - i);
else RL[i] = 1;
while (i - RL[i] >= 0 && i + RL[i] < n && a[i - RL[i]] == a[i + RL[i]])
RL[i]++;
if (RL[i] + i - 1 > r) { r = RL[i] + i - 1; p = i; }
}
FOR (i, 0, n) --RL[i];
}

struct RMQ {
int f[22][N];
inline int highbit(int x) { return 31 - __builtin_clz(x); }
void init(int* v, int n) {
FOR (i, 0, n) f[0][i] = v[i];
FOR (x, 1, highbit(n) + 1)
FOR (i, 0, n - (1 << x) + 1)
f[x][i] = max(f[x - 1][i], f[x - 1][i + (1 << (x - 1))]);
}
int get_max(int l, int r) {
assert(l <= r);
int t = highbit(r - l + 1);
return max(f[t][l], f[t][r - (1 << t) + 1]);
}
} rmq;

char s[N];
int a[N];
int main() {
int n, m; cin >> n; m = n * 4 + 1;
scanf("%s", s); FOR (i, 0, n) s[i + n] = s[i];
FOR (i, 0, n * 2) a[i * 2 + 1] = s[i] - 'a';
FOR (i, 0, n * 2 + 1) a[i * 2] = 26;
manacher(a, m);
FOR (i, 0, m) dbg(i, RL[i]);
rmq.init(RL, m);

FOR (i, 0, n) {
int L = i * 2 + 1, R = (i + n - 1) * 2 + 1;
int ans = -1, l = 1, r = n;
while (l <= r) {
int m = (l + r) / 2;
if (rmq.get_max(L + m - 1, R - m + 1) >= m) {
ans = m; l = m + 1;
} else r = m - 1;
}
printf("%d\n", ans);
}
}