【题解】HackerRank-Circular Palindromes

Posted on In Disqus:

题目

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);
    }
}