Manacher Algorithm
(string/manacher.hpp)
- View this file on GitHub
- Last update: 2026-06-21 02:43:08+09:00
- Include:
#include "string/manacher.hpp"
Overview
manacher(sequence) finds every maximal odd- and even-length palindrome in
linear time. The result also answers whether any substring is a palindrome in
$O(1)$.
The function is generic over indexable sequences with comparable elements.
Result
ManacherResult contains:
| Member / Method | Meaning | Complexity |
|---|---|---|
odd[i] |
Radius including center i; palindrome [i - odd[i] + 1, i + odd[i]). |
Access $O(1)$ |
even[i] |
Radius centered between i - 1 and i; palindrome [i - even[i], i + even[i]). |
Access $O(1)$ |
size() |
Returns the original sequence length. | $O(1)$ |
empty() |
Returns whether the sequence is empty. | $O(1)$ |
is_palindrome(l, r) |
Returns whether [l, r) is a palindrome. |
$O(1)$ |
longest_length() |
Returns the longest palindromic substring length. | $O(N)$ |
Construction takes $O(N)$ time and space.
Example
#include "string/manacher.hpp"
#include <iostream>
#include <string>
int main() {
auto palindromes = m1une::string::manacher(std::string("abacaba"));
std::cout << palindromes.longest_length() << "\n"; // 7
std::cout << palindromes.is_palindrome(1, 6) << "\n"; // 1
std::cout << palindromes.is_palindrome(0, 4) << "\n"; // 0
}
Required by
Verified with
Code
#ifndef M1UNE_STRING_MANACHER_HPP
#define M1UNE_STRING_MANACHER_HPP 1
#include <algorithm>
#include <cassert>
#include <vector>
namespace m1une {
namespace string {
struct ManacherResult {
// odd[i] is the radius including center i.
// The palindrome is [i - odd[i] + 1, i + odd[i]).
std::vector<int> odd;
// even[i] is the radius centered between i - 1 and i.
// The palindrome is [i - even[i], i + even[i]).
std::vector<int> even;
int size() const {
return int(odd.size());
}
bool empty() const {
return odd.empty();
}
bool is_palindrome(int left, int right) const {
int n = size();
assert(0 <= left && left <= right && right <= n);
int length = right - left;
if (length == 0) return true;
if (length & 1) {
int center = (left + right) / 2;
return length / 2 + 1 <= odd[center];
}
int center = (left + right) / 2;
return length / 2 <= even[center];
}
int longest_length() const {
int result = 0;
for (int radius : odd) result = std::max(result, 2 * radius - 1);
for (int radius : even) result = std::max(result, 2 * radius);
return result;
}
};
template <class Sequence>
ManacherResult manacher(const Sequence& sequence) {
int n = int(sequence.size());
ManacherResult result;
result.odd.assign(n, 0);
result.even.assign(n, 0);
int left = 0;
int right = -1;
for (int i = 0; i < n; i++) {
int radius = i > right ? 1 : std::min(result.odd[left + right - i], right - i + 1);
while (
0 <= i - radius &&
i + radius < n &&
sequence[i - radius] == sequence[i + radius]
) {
radius++;
}
result.odd[i] = radius;
if (right < i + radius - 1) {
left = i - radius + 1;
right = i + radius - 1;
}
}
left = 0;
right = -1;
for (int i = 0; i < n; i++) {
int radius = i > right ? 0 : std::min(result.even[left + right - i + 1], right - i + 1);
while (
0 <= i - radius - 1 &&
i + radius < n &&
sequence[i - radius - 1] == sequence[i + radius]
) {
radius++;
}
result.even[i] = radius;
if (right < i + radius - 1) {
left = i - radius;
right = i + radius - 1;
}
}
return result;
}
} // namespace string
} // namespace m1une
#endif // M1UNE_STRING_MANACHER_HPP#line 1 "string/manacher.hpp"
#include <algorithm>
#include <cassert>
#include <vector>
namespace m1une {
namespace string {
struct ManacherResult {
// odd[i] is the radius including center i.
// The palindrome is [i - odd[i] + 1, i + odd[i]).
std::vector<int> odd;
// even[i] is the radius centered between i - 1 and i.
// The palindrome is [i - even[i], i + even[i]).
std::vector<int> even;
int size() const {
return int(odd.size());
}
bool empty() const {
return odd.empty();
}
bool is_palindrome(int left, int right) const {
int n = size();
assert(0 <= left && left <= right && right <= n);
int length = right - left;
if (length == 0) return true;
if (length & 1) {
int center = (left + right) / 2;
return length / 2 + 1 <= odd[center];
}
int center = (left + right) / 2;
return length / 2 <= even[center];
}
int longest_length() const {
int result = 0;
for (int radius : odd) result = std::max(result, 2 * radius - 1);
for (int radius : even) result = std::max(result, 2 * radius);
return result;
}
};
template <class Sequence>
ManacherResult manacher(const Sequence& sequence) {
int n = int(sequence.size());
ManacherResult result;
result.odd.assign(n, 0);
result.even.assign(n, 0);
int left = 0;
int right = -1;
for (int i = 0; i < n; i++) {
int radius = i > right ? 1 : std::min(result.odd[left + right - i], right - i + 1);
while (
0 <= i - radius &&
i + radius < n &&
sequence[i - radius] == sequence[i + radius]
) {
radius++;
}
result.odd[i] = radius;
if (right < i + radius - 1) {
left = i - radius + 1;
right = i + radius - 1;
}
}
left = 0;
right = -1;
for (int i = 0; i < n; i++) {
int radius = i > right ? 0 : std::min(result.even[left + right - i + 1], right - i + 1);
while (
0 <= i - radius - 1 &&
i + radius < n &&
sequence[i - radius - 1] == sequence[i + radius]
) {
radius++;
}
result.even[i] = radius;
if (right < i + radius - 1) {
left = i - radius;
right = i + radius - 1;
}
}
return result;
}
} // namespace string
} // namespace m1une