Palindrome Lexicographical Order
(string/palindrome_lexicographical_order.hpp)
- View this file on GitHub
- Last update: 2026-07-25 23:09:52+09:00
- Include:
#include "string/palindrome_lexicographical_order.hpp"
Overview
PalindromeLexicographicalOrder indexes every distinct nonempty palindromic
substring of one sequence. It assigns zero-based ranks after sorting the
palindromes lexicographically and supports both directions:
- find the rank of a palindrome or eertree node;
- recover the node, a representative occurrence, or a copy of the palindrome at a given rank.
The index combines an eertree with a suffix array. It does not count duplicate occurrences separately.
#include "string/palindrome_lexicographical_order.hpp"
Template Parameters
template <
class Sequence = std::string,
int AlphabetSize = 26,
int FirstCharacter = 'a'
>
struct PalindromeLexicographicalOrder;
Sequence must provide size(), random-access iterators, and operator[],
and it must be constructible from a pair of its iterators. Its value type must
be convertible to int and sortable. Symbols must belong to the contiguous range
[FirstCharacter, FirstCharacter + AlphabetSize).
The default specialization accepts lowercase English strings. For a vector
whose values are in [0, 4), use
PalindromeLexicographicalOrder<std::vector<int>, 4, 0>.
Methods
Let N be the sequence length, D the number of distinct nonempty
palindromic substrings, and L the length of a queried or returned
palindrome.
| Method | Description | Complexity |
|---|---|---|
PalindromeLexicographicalOrder() |
Constructs an empty index. | $O(1)$ |
PalindromeLexicographicalOrder(sequence) |
Copies or moves the sequence and builds its index. | $O(N \cdot AlphabetSize + N \log N)$ time and $O(N \cdot AlphabetSize)$ memory |
int size() const |
Returns D. |
$O(1)$ |
bool empty() const |
Returns whether D == 0. |
$O(1)$ |
int text_length() const |
Returns N. |
$O(1)$ |
const Sequence& sequence() const |
Returns the indexed sequence. | $O(1)$ |
const eertree_type& eertree() const |
Returns the underlying eertree. | $O(1)$ |
const vector<node_id>& nodes_in_order() const |
Returns all real eertree nodes in increasing lexicographic order. | $O(1)$ |
int order_of_node(id) const |
Returns the zero-based rank of a real eertree node. | $O(1)$ |
node_id node_by_order(order) const |
Returns the eertree node having the given rank. | $O(1)$ |
node_id find(palindrome) const |
Returns its node, or eertree_type::null_node if it is not a nonempty palindromic substring. |
$O(L)$ |
bool contains(palindrome) const |
Tests whether it is indexed. | $O(L)$ |
int order_of_palindrome(palindrome) const |
Returns its rank, or -1 if it is not indexed. |
$O(L)$ |
pair<int, int> representative_occurrence(order) const |
Returns a half-open occurrence interval of the ranked palindrome. | $O(1)$ |
Sequence palindrome(order) const |
Returns a copy of the ranked palindrome. | $O(L)$ |
Sequence kth(order) const |
Alias of palindrome(order). |
$O(L)$ |
order_of_node, node_by_order, representative_occurrence, palindrome,
and kth assert that their node or order is valid. The empty string is not
indexed. All query methods are non-mutating.
For a constant alphabet, construction takes $O(N \log N)$ time. It uses $O(N)$ additional memory outside the fixed transition arrays stored by the eertree.
Example
#include "string/palindrome_lexicographical_order.hpp"
#include <iostream>
#include <string>
int main() {
m1une::string::PalindromeLexicographicalOrder<> index(
std::string("abacaba")
);
std::cout << index.order_of_palindrome(std::string("aca")) << '\n';
for (int order = 0; order < index.size(); order++) {
std::cout << order << ' ' << index.palindrome(order) << '\n';
}
}
Depends on
Required by
Verified with
Code
#ifndef M1UNE_STRING_PALINDROME_LEXICOGRAPHICAL_ORDER_HPP
#define M1UNE_STRING_PALINDROME_LEXICOGRAPHICAL_ORDER_HPP 1
#include <algorithm>
#include <cassert>
#include <string>
#include <utility>
#include <vector>
#include "eertree.hpp"
#include "suffix_array.hpp"
namespace m1une {
namespace string {
// Indexes the distinct nonempty palindromic substrings of one sequence.
template <
class Sequence = std::string,
int AlphabetSize = 26,
int FirstCharacter = 'a'
>
struct PalindromeLexicographicalOrder {
static_assert(0 < AlphabetSize);
using eertree_type = Eertree<AlphabetSize, FirstCharacter>;
using node_id = typename eertree_type::node_id;
private:
Sequence _sequence;
eertree_type _eertree;
std::vector<node_id> _nodes_in_order;
std::vector<int> _order_of_node;
template <class Symbol>
static int symbol_index(const Symbol& symbol) {
int index = int(symbol) - FirstCharacter;
assert(0 <= index && index < AlphabetSize);
return index;
}
void build_order() {
const int node_count = _eertree.node_count();
std::vector<std::vector<node_id>> suffix_children(node_count);
for (node_id id = 0; id < node_count; id++) {
if (id == eertree_type::odd_root) continue;
suffix_children[_eertree.node(id).suffix_link].push_back(id);
}
std::vector<int> enter(node_count);
std::vector<int> leave(node_count);
std::vector<std::pair<node_id, bool>> stack;
stack.reserve(2 * node_count);
stack.emplace_back(eertree_type::odd_root, false);
int timer = 0;
while (!stack.empty()) {
auto [id, exiting] = stack.back();
stack.pop_back();
if (exiting) {
leave[id] = timer;
continue;
}
enter[id] = timer++;
stack.emplace_back(id, true);
const auto& children = suffix_children[id];
for (int i = int(children.size()) - 1; i >= 0; i--) {
stack.emplace_back(children[i], false);
}
}
std::vector<int> suffixes = suffix_array(_sequence);
std::vector<int> suffix_rank(_sequence.size());
for (int rank = 0; rank < int(suffixes.size()); rank++) {
suffix_rank[suffixes[rank]] = rank;
}
_nodes_in_order.resize(_eertree.size());
for (int i = 0; i < _eertree.size(); i++) {
_nodes_in_order[i] = i + 2;
}
auto is_ancestor = [&](node_id ancestor, node_id descendant) {
return
enter[ancestor] <= enter[descendant] &&
leave[descendant] <= leave[ancestor];
};
std::sort(
_nodes_in_order.begin(),
_nodes_in_order.end(),
[&](node_id first, node_id second) {
if (first == second) return false;
// A palindromic prefix is also a palindromic suffix, so prefix
// cases are exactly the ancestor cases in the suffix-link tree.
if (is_ancestor(first, second)) return true;
if (is_ancestor(second, first)) return false;
// Otherwise the first mismatch occurs inside both substrings,
// and the ranks of representative suffixes give their order.
int first_start = _eertree.first_occurrence(first).first;
int second_start = _eertree.first_occurrence(second).first;
return suffix_rank[first_start] < suffix_rank[second_start];
}
);
_order_of_node.assign(node_count, -1);
for (int order = 0; order < size(); order++) {
_order_of_node[_nodes_in_order[order]] = order;
}
}
public:
PalindromeLexicographicalOrder() : _order_of_node(2, -1) {}
explicit PalindromeLexicographicalOrder(const Sequence& sequence)
: _sequence(sequence), _eertree(_sequence) {
build_order();
}
explicit PalindromeLexicographicalOrder(Sequence&& sequence)
: _sequence(std::move(sequence)), _eertree(_sequence) {
build_order();
}
int size() const {
return int(_nodes_in_order.size());
}
bool empty() const {
return _nodes_in_order.empty();
}
int text_length() const {
return int(_sequence.size());
}
const Sequence& sequence() const {
return _sequence;
}
const eertree_type& eertree() const {
return _eertree;
}
const std::vector<node_id>& nodes_in_order() const {
return _nodes_in_order;
}
int order_of_node(node_id id) const {
assert(2 <= id && id < _eertree.node_count());
return _order_of_node[id];
}
node_id node_by_order(int order) const {
assert(0 <= order && order < size());
return _nodes_in_order[order];
}
template <class Palindrome>
node_id find(const Palindrome& palindrome) const {
const int length = int(palindrome.size());
if (length == 0) return eertree_type::null_node;
for (int i = 0; i < length / 2; i++) {
if (palindrome[i] != palindrome[length - 1 - i]) {
return eertree_type::null_node;
}
}
node_id id =
length & 1 ? eertree_type::odd_root : eertree_type::even_root;
for (int i = (length - 1) / 2; i >= 0; i--) {
int symbol = symbol_index(palindrome[i]);
id = _eertree.node(id).next[symbol];
if (id == eertree_type::null_node) return id;
}
return id;
}
template <class Palindrome>
bool contains(const Palindrome& palindrome) const {
return find(palindrome) != eertree_type::null_node;
}
template <class Palindrome>
int order_of_palindrome(const Palindrome& palindrome) const {
node_id id = find(palindrome);
return id == eertree_type::null_node ? -1 : order_of_node(id);
}
std::pair<int, int> representative_occurrence(int order) const {
return _eertree.first_occurrence(node_by_order(order));
}
Sequence palindrome(int order) const {
auto [left, right] = representative_occurrence(order);
return Sequence(_sequence.begin() + left, _sequence.begin() + right);
}
Sequence kth(int order) const {
return palindrome(order);
}
};
} // namespace string
} // namespace m1une
#endif // M1UNE_STRING_PALINDROME_LEXICOGRAPHICAL_ORDER_HPP#line 1 "string/palindrome_lexicographical_order.hpp"
#include <algorithm>
#include <cassert>
#include <string>
#include <utility>
#include <vector>
#line 1 "string/eertree.hpp"
#include <array>
#line 6 "string/eertree.hpp"
#include <cstddef>
#include <limits>
#line 10 "string/eertree.hpp"
namespace m1une {
namespace string {
template <int AlphabetSize = 26, int FirstCharacter = 'a'>
struct Eertree {
static_assert(0 < AlphabetSize);
using node_id = int;
static constexpr node_id even_root = 0;
static constexpr node_id odd_root = 1;
static constexpr node_id null_node = -1;
struct Node {
std::array<node_id, AlphabetSize> next;
node_id suffix_link;
node_id series_link;
int length;
int diff;
int suffix_count;
int first_end;
long long suffix_occurrences;
Node(int length_value = 0, node_id suffix_link_value = even_root, node_id series_link_value = even_root)
: suffix_link(suffix_link_value),
series_link(series_link_value),
length(length_value),
diff(0),
suffix_count(0),
first_end(0),
suffix_occurrences(0) {
next.fill(null_node);
}
};
private:
std::vector<Node> _nodes;
std::vector<int> _text;
std::vector<node_id> _longest_suffix;
node_id _last;
template <class Symbol>
static int symbol_index(const Symbol& symbol) {
int index = int(symbol) - FirstCharacter;
assert(0 <= index && index < AlphabetSize);
return index;
}
node_id find_extendable(node_id node, int position, int symbol) const {
while (true) {
int length = _nodes[node].length;
int left = position - length - 1;
if (0 <= left && _text[left] == symbol) return node;
node = _nodes[node].suffix_link;
}
}
node_id new_node(int length) {
assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
_nodes.emplace_back(length);
return int(_nodes.size()) - 1;
}
public:
Eertree() {
clear();
}
template <class Sequence>
explicit Eertree(const Sequence& sequence) {
clear();
build(sequence);
}
int size() const {
return int(_nodes.size()) - 2;
}
bool empty() const {
return size() == 0;
}
int node_count() const {
return int(_nodes.size());
}
int text_length() const {
return int(_text.size());
}
node_id last() const {
return _last;
}
int longest_suffix_length() const {
return _nodes[_last].length;
}
const Node& node(node_id id) const {
assert(0 <= id && id < node_count());
return _nodes[id];
}
const std::vector<Node>& nodes() const {
return _nodes;
}
node_id longest_suffix_node(int prefix_length) const {
assert(1 <= prefix_length && prefix_length <= text_length());
return _longest_suffix[prefix_length - 1];
}
const std::vector<node_id>& longest_suffix_nodes() const {
return _longest_suffix;
}
template <class Callback>
void for_each_suffix(node_id id, Callback callback) const {
assert(0 <= id && id < node_count());
while (id >= 2) {
callback(id);
id = _nodes[id].suffix_link;
}
}
template <class Callback>
void for_each_suffix(Callback callback) const {
for_each_suffix(_last, callback);
}
void reserve(std::size_t text_capacity) {
_text.reserve(text_capacity);
_longest_suffix.reserve(text_capacity);
_nodes.reserve(text_capacity + 2);
}
void clear() {
_nodes.clear();
_nodes.emplace_back(0, odd_root, even_root);
_nodes.emplace_back(-1, odd_root, odd_root);
_text.clear();
_longest_suffix.clear();
_last = even_root;
}
template <class Symbol>
node_id add(const Symbol& value) {
int symbol = symbol_index(value);
int position = int(_text.size());
_text.push_back(symbol);
node_id current = find_extendable(_last, position, symbol);
node_id next = _nodes[current].next[symbol];
if (next == null_node) {
int length = _nodes[current].length + 2;
next = new_node(length);
_nodes[current].next[symbol] = next;
node_id suffix_link = even_root;
if (length != 1) {
node_id candidate = find_extendable(_nodes[current].suffix_link, position, symbol);
suffix_link = _nodes[candidate].next[symbol];
assert(suffix_link != null_node);
}
Node& created = _nodes[next];
created.suffix_link = suffix_link;
created.diff = created.length - _nodes[suffix_link].length;
created.series_link =
created.diff == _nodes[suffix_link].diff ? _nodes[suffix_link].series_link : suffix_link;
created.suffix_count = _nodes[suffix_link].suffix_count + 1;
created.first_end = position + 1;
}
_last = next;
_nodes[_last].suffix_occurrences++;
_longest_suffix.push_back(_last);
return _last;
}
template <class Sequence>
void build(const Sequence& sequence) {
for (const auto& symbol : sequence) add(symbol);
}
std::vector<long long> occurrence_counts() const {
std::vector<long long> result(_nodes.size(), 0);
for (node_id id = 0; id < node_count(); id++) {
result[id] = _nodes[id].suffix_occurrences;
}
for (node_id id = node_count() - 1; id >= 2; id--) {
result[_nodes[id].suffix_link] += result[id];
}
return result;
}
std::pair<int, int> first_occurrence(node_id id) const {
assert(2 <= id && id < node_count());
int end = _nodes[id].first_end;
return {end - _nodes[id].length, end};
}
};
template <int AlphabetSize = 26, int FirstCharacter = 'a'>
using PalindromicTree = Eertree<AlphabetSize, FirstCharacter>;
} // namespace string
} // namespace m1une
#line 1 "string/suffix_array.hpp"
#line 6 "string/suffix_array.hpp"
#include <numeric>
#line 8 "string/suffix_array.hpp"
#include <type_traits>
#line 10 "string/suffix_array.hpp"
namespace m1une {
namespace string {
namespace detail {
template <class Sequence>
std::vector<int> suffix_array_impl(const Sequence& sequence) {
int n = int(sequence.size());
if (n == 0) return {};
using Value = std::remove_cv_t<std::remove_reference_t<decltype(sequence[0])>>;
std::vector<Value> sorted(sequence.begin(), sequence.end());
std::sort(sorted.begin(), sorted.end());
sorted.erase(std::unique(sorted.begin(), sorted.end()), sorted.end());
int length = n + 1;
std::vector<int> order(length);
std::vector<int> rank(length);
std::vector<int> key(length);
key[n] = 0;
for (int i = 0; i < n; i++) {
key[i] = int(std::lower_bound(sorted.begin(), sorted.end(), sequence[i]) - sorted.begin()) + 1;
}
int alphabet = int(sorted.size()) + 1;
std::vector<int> count(std::max(length, alphabet), 0);
for (int value : key) count[value]++;
for (int i = 1; i < alphabet; i++) count[i] += count[i - 1];
for (int i = length - 1; i >= 0; i--) order[--count[key[i]]] = i;
int classes = 1;
rank[order[0]] = 0;
for (int i = 1; i < length; i++) {
if (key[order[i - 1]] != key[order[i]]) classes++;
rank[order[i]] = classes - 1;
}
std::vector<int> shifted(length);
std::vector<int> next_rank(length);
for (long long half = 1; half < length; half <<= 1) {
for (int i = 0; i < length; i++) {
long long position = order[i] - half;
if (position < 0) position += length;
shifted[i] = int(position);
}
count.assign(classes, 0);
for (int position : shifted) count[rank[position]]++;
for (int i = 1; i < classes; i++) count[i] += count[i - 1];
for (int i = length - 1; i >= 0; i--) {
int position = shifted[i];
order[--count[rank[position]]] = position;
}
int next_classes = 1;
next_rank[order[0]] = 0;
for (int i = 1; i < length; i++) {
int current = order[i];
int previous = order[i - 1];
int current_second = int((current + half) % length);
int previous_second = int((previous + half) % length);
if (
rank[current] != rank[previous] ||
rank[current_second] != rank[previous_second]
) {
next_classes++;
}
next_rank[current] = next_classes - 1;
}
rank.swap(next_rank);
classes = next_classes;
if (classes == length) break;
}
std::vector<int> suffixes(n);
for (int i = 0; i < n; i++) suffixes[i] = order[i + 1];
return suffixes;
}
} // namespace detail
template <class Sequence>
std::vector<int> suffix_array(const Sequence& sequence) {
return detail::suffix_array_impl(sequence);
}
inline std::vector<int> suffix_array(const std::string& text) {
std::vector<unsigned char> values;
values.reserve(text.size());
for (unsigned char character : text) values.push_back(character);
return detail::suffix_array_impl(values);
}
template <class Sequence>
std::vector<int> lcp_array(const Sequence& sequence, const std::vector<int>& suffixes) {
int n = int(sequence.size());
assert(int(suffixes.size()) == n);
if (n == 0) return {};
std::vector<int> rank(n);
for (int i = 0; i < n; i++) {
assert(0 <= suffixes[i] && suffixes[i] < n);
rank[suffixes[i]] = i;
}
std::vector<int> lcp(n - 1);
int common = 0;
for (int i = 0; i < n; i++) {
int position = rank[i];
if (position == n - 1) {
common = 0;
continue;
}
int j = suffixes[position + 1];
while (
i + common < n &&
j + common < n &&
sequence[i + common] == sequence[j + common]
) {
common++;
}
lcp[position] = common;
if (common > 0) common--;
}
return lcp;
}
} // namespace string
} // namespace m1une
#line 12 "string/palindrome_lexicographical_order.hpp"
namespace m1une {
namespace string {
// Indexes the distinct nonempty palindromic substrings of one sequence.
template <
class Sequence = std::string,
int AlphabetSize = 26,
int FirstCharacter = 'a'
>
struct PalindromeLexicographicalOrder {
static_assert(0 < AlphabetSize);
using eertree_type = Eertree<AlphabetSize, FirstCharacter>;
using node_id = typename eertree_type::node_id;
private:
Sequence _sequence;
eertree_type _eertree;
std::vector<node_id> _nodes_in_order;
std::vector<int> _order_of_node;
template <class Symbol>
static int symbol_index(const Symbol& symbol) {
int index = int(symbol) - FirstCharacter;
assert(0 <= index && index < AlphabetSize);
return index;
}
void build_order() {
const int node_count = _eertree.node_count();
std::vector<std::vector<node_id>> suffix_children(node_count);
for (node_id id = 0; id < node_count; id++) {
if (id == eertree_type::odd_root) continue;
suffix_children[_eertree.node(id).suffix_link].push_back(id);
}
std::vector<int> enter(node_count);
std::vector<int> leave(node_count);
std::vector<std::pair<node_id, bool>> stack;
stack.reserve(2 * node_count);
stack.emplace_back(eertree_type::odd_root, false);
int timer = 0;
while (!stack.empty()) {
auto [id, exiting] = stack.back();
stack.pop_back();
if (exiting) {
leave[id] = timer;
continue;
}
enter[id] = timer++;
stack.emplace_back(id, true);
const auto& children = suffix_children[id];
for (int i = int(children.size()) - 1; i >= 0; i--) {
stack.emplace_back(children[i], false);
}
}
std::vector<int> suffixes = suffix_array(_sequence);
std::vector<int> suffix_rank(_sequence.size());
for (int rank = 0; rank < int(suffixes.size()); rank++) {
suffix_rank[suffixes[rank]] = rank;
}
_nodes_in_order.resize(_eertree.size());
for (int i = 0; i < _eertree.size(); i++) {
_nodes_in_order[i] = i + 2;
}
auto is_ancestor = [&](node_id ancestor, node_id descendant) {
return
enter[ancestor] <= enter[descendant] &&
leave[descendant] <= leave[ancestor];
};
std::sort(
_nodes_in_order.begin(),
_nodes_in_order.end(),
[&](node_id first, node_id second) {
if (first == second) return false;
// A palindromic prefix is also a palindromic suffix, so prefix
// cases are exactly the ancestor cases in the suffix-link tree.
if (is_ancestor(first, second)) return true;
if (is_ancestor(second, first)) return false;
// Otherwise the first mismatch occurs inside both substrings,
// and the ranks of representative suffixes give their order.
int first_start = _eertree.first_occurrence(first).first;
int second_start = _eertree.first_occurrence(second).first;
return suffix_rank[first_start] < suffix_rank[second_start];
}
);
_order_of_node.assign(node_count, -1);
for (int order = 0; order < size(); order++) {
_order_of_node[_nodes_in_order[order]] = order;
}
}
public:
PalindromeLexicographicalOrder() : _order_of_node(2, -1) {}
explicit PalindromeLexicographicalOrder(const Sequence& sequence)
: _sequence(sequence), _eertree(_sequence) {
build_order();
}
explicit PalindromeLexicographicalOrder(Sequence&& sequence)
: _sequence(std::move(sequence)), _eertree(_sequence) {
build_order();
}
int size() const {
return int(_nodes_in_order.size());
}
bool empty() const {
return _nodes_in_order.empty();
}
int text_length() const {
return int(_sequence.size());
}
const Sequence& sequence() const {
return _sequence;
}
const eertree_type& eertree() const {
return _eertree;
}
const std::vector<node_id>& nodes_in_order() const {
return _nodes_in_order;
}
int order_of_node(node_id id) const {
assert(2 <= id && id < _eertree.node_count());
return _order_of_node[id];
}
node_id node_by_order(int order) const {
assert(0 <= order && order < size());
return _nodes_in_order[order];
}
template <class Palindrome>
node_id find(const Palindrome& palindrome) const {
const int length = int(palindrome.size());
if (length == 0) return eertree_type::null_node;
for (int i = 0; i < length / 2; i++) {
if (palindrome[i] != palindrome[length - 1 - i]) {
return eertree_type::null_node;
}
}
node_id id =
length & 1 ? eertree_type::odd_root : eertree_type::even_root;
for (int i = (length - 1) / 2; i >= 0; i--) {
int symbol = symbol_index(palindrome[i]);
id = _eertree.node(id).next[symbol];
if (id == eertree_type::null_node) return id;
}
return id;
}
template <class Palindrome>
bool contains(const Palindrome& palindrome) const {
return find(palindrome) != eertree_type::null_node;
}
template <class Palindrome>
int order_of_palindrome(const Palindrome& palindrome) const {
node_id id = find(palindrome);
return id == eertree_type::null_node ? -1 : order_of_node(id);
}
std::pair<int, int> representative_occurrence(int order) const {
return _eertree.first_occurrence(node_by_order(order));
}
Sequence palindrome(int order) const {
auto [left, right] = representative_occurrence(order);
return Sequence(_sequence.begin() + left, _sequence.begin() + right);
}
Sequence kth(int order) const {
return palindrome(order);
}
};
} // namespace string
} // namespace m1une