manacher.hpp¶
在线性时间返回每个字符和间隙中心的最长回文长度；直接比较原序列，无需分隔符或字符复制。
Complexity: Time: \(O(n)\), for constant-time equality comparisons. Space: \(O(n)\) returned lengths and \(O(1)\) auxiliary space.
AC 记录：enumerate_palindromes。
Implementation¶
当前头文件，省略 include guard；依赖见 #include。
/// @complexity Time: O(n), for constant-time equality comparisons.
/// Space: O(n) returned lengths and O(1) auxiliary space.
#include <algorithm>
#include <string>
#include <vector>
namespace noya {
namespace manacher_internal {
template <class Seq> std::vector<int> radii(const Seq &s) {
int n = int(s.size());
if (n == 0)
return {};
std::vector<int> p(2 * n - 1);
// Doubled centers: even c is a character, odd c is a gap.
// [m - p[m], m + p[m]] are virtual boundaries; r = m + p[m].
for (int c = 0, m = 0, r = 0; c < 2 * n - 1; ++c) {
int k = c < r ? std::min(p[m - (c - m)], r - c) : 1 - (c & 1);
while (c - k - 1 >= 0 && c + k + 1 < 2 * n &&
s[(c - k - 1) / 2] == s[(c + k + 1) / 2])
k += 2;
p[c] = k;
if (c + k > r) {
m = c;
r = c + k;
}
}
return p;
}
} // namespace manacher_internal
/// @brief Longest palindrome lengths at all character and gap centers.
/// @return 2n-1 entries: p[2i] is odd, p[2i+1] is even; empty input gives {}.
/// Symbols need only equality; 2n must fit in int.
template <class T> std::vector<int> manacher(const std::vector<T> &s) {
return manacher_internal::radii(s);
}
inline std::vector<int> manacher(const std::string &s) {
return manacher_internal::radii(s);
}
} // namespace noya
// NOYA_MANACHER_HPP
#ifndef NOYA_MANACHER_HPP
#define NOYA_MANACHER_HPP 1
/// @complexity Time: O(n), for constant-time equality comparisons.
/// Space: O(n) returned lengths and O(1) auxiliary space.
#include <algorithm>
#include <string>
#include <vector>
namespace noya {
namespace manacher_internal {
template <class Seq> std::vector<int> radii(const Seq &s) {
int n = int(s.size());
if (n == 0)
return {};
std::vector<int> p(2 * n - 1);
// Doubled centers: even c is a character, odd c is a gap.
// [m - p[m], m + p[m]] are virtual boundaries; r = m + p[m].
for (int c = 0, m = 0, r = 0; c < 2 * n - 1; ++c) {
int k = c < r ? std::min(p[m - (c - m)], r - c) : 1 - (c & 1);
while (c - k - 1 >= 0 && c + k + 1 < 2 * n &&
s[(c - k - 1) / 2] == s[(c + k + 1) / 2])
k += 2;
p[c] = k;
if (c + k > r) {
m = c;
r = c + k;
}
}
return p;
}
} // namespace manacher_internal
/// @brief Longest palindrome lengths at all character and gap centers.
/// @return 2n-1 entries: p[2i] is odd, p[2i+1] is even; empty input gives {}.
/// Symbols need only equality; 2n must fit in int.
template <class T> std::vector<int> manacher(const std::vector<T> &s) {
return manacher_internal::radii(s);
}
inline std::vector<int> manacher(const std::string &s) {
return manacher_internal::radii(s);
}
} // namespace noya
#endif // NOYA_MANACHER_HPP
/// @complexity Time: O(n), for constant-time equality comparisons.
/// Space: O(n) returned lengths and O(1) auxiliary space.
#include <algorithm>
#include <string>
#include <vector>
namespace noya {
namespace manacher_internal {
template <class Seq> std::vector<int> radii(const Seq &s) {
int n = int(s.size());
if (n == 0)
return {};
std::vector<int> p(2 * n - 1);
// Doubled centers: even c is a character, odd c is a gap.
// [m - p[m], m + p[m]] are virtual boundaries; r = m + p[m].
for (int c = 0, m = 0, r = 0; c < 2 * n - 1; ++c) {
int k = c < r ? std::min(p[m - (c - m)], r - c) : 1 - (c & 1);
while (c - k - 1 >= 0 && c + k + 1 < 2 * n &&
s[(c - k - 1) / 2] == s[(c + k + 1) / 2])
k += 2;
p[c] = k;
if (c + k > r) {
m = c;
r = c + k;
}
}
return p;
}
} // namespace manacher_internal
/// @brief Longest palindrome lengths at all character and gap centers.
/// @return 2n-1 entries: p[2i] is odd, p[2i+1] is even; empty input gives {}.
/// Symbols need only equality; 2n must fit in int.
template <class T> std::vector<int> manacher(const std::vector<T> &s) {
return manacher_internal::radii(s);
}
inline std::vector<int> manacher(const std::string &s) {
return manacher_internal::radii(s);
}
} // namespace noya
// NOYA_MANACHER_HPP