deque_palindromic_tree.hpp¶
Maintain all distinct palindromic substrings under pushes and pops at both ends. Every active palindrome is a node with a suffix link, while each text position stores the longest palindrome beginning or ending there. A quick link skips suffix-link runs whose next extension character is the same, so a new extendable boundary palindrome is found logarithmically. Surface counters and incoming suffix-link counters identify a node exactly when its last occurrence disappears, allowing an end deletion to undo only local certificates. Two reversed vectors provide amortized constant-time deque rebalancing while retaining indexed character access.
Verified by palindromes_in_deque.
支持在字符串两端加入字符，并维护不同回文子串与最长回文信息。
Implementation¶
#ifndef NOYA_DEQUE_PALINDROMIC_TREE_HPP
#define NOYA_DEQUE_PALINDROMIC_TREE_HPP 1
/// @complexity Time: push O(log n + log sigma) worst case, pop O(log sigma)
/// amortized, and query O(1). Space: O(n), where n is the current length and
/// sigma is the number of distinct character values.
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <iterator>
#include <map>
#include <memory>
#include <utility>
#include <vector>
namespace noya {
namespace deque_palindromic_tree_internal {
template <class T> class amortized_deque {
std::vector<T> left_, right_;
static void move_half(std::vector<T> &target, std::vector<T> &source) {
assert(target.empty() && !source.empty());
std::size_t moved = (source.size() + 1) / 2;
std::move(source.rend() - moved, source.rend(), std::back_inserter(target));
source.erase(source.begin(), source.begin() + moved);
}
public:
int size() const { return int(left_.size() + right_.size()); }
bool empty() const { return left_.empty() && right_.empty(); }
T &operator[](int index) {
assert(0 <= index && index < size());
return index < int(left_.size())
? left_[left_.size() - 1 - std::size_t(index)]
: right_[std::size_t(index) - left_.size()];
}
const T &operator[](int index) const {
assert(0 <= index && index < size());
return index < int(left_.size())
? left_[left_.size() - 1 - std::size_t(index)]
: right_[std::size_t(index) - left_.size()];
}
T &front() { return left_.empty() ? right_.front() : left_.back(); }
const T &front() const {
return left_.empty() ? right_.front() : left_.back();
}
T &back() { return right_.empty() ? left_.front() : right_.back(); }
const T &back() const {
return right_.empty() ? left_.front() : right_.back();
}
void push_front(const T &value) { left_.push_back(value); }
void push_front(T &&value) { left_.push_back(std::move(value)); }
void push_back(const T &value) { right_.push_back(value); }
void push_back(T &&value) { right_.push_back(std::move(value)); }
void pop_front() {
assert(!empty());
if (left_.empty()) {
move_half(left_, right_);
}
left_.pop_back();
}
void pop_back() {
assert(!empty());
if (right_.empty()) {
move_half(right_, left_);
}
right_.pop_back();
}
};
} // namespace deque_palindromic_tree_internal
/// @brief Maintain all distinct palindromic substrings under pushes and pops
/// at both ends. Every active palindrome is a node with a suffix link, while
/// each text position stores the longest palindrome beginning or ending there.
/// A quick link skips suffix-link runs whose next extension character is the
/// same, so a new extendable boundary palindrome is found logarithmically.
/// Surface counters and incoming suffix-link counters identify a node exactly
/// when its last occurrence disappears, allowing an end deletion to undo only
/// local certificates. Two reversed vectors provide amortized constant-time
/// deque rebalancing while retaining indexed character access.
template <class Char = int, class Compare = std::less<Char>>
class deque_palindromic_tree {
struct node {
node *parent = nullptr;
node *link = nullptr;
node *quick = nullptr;
std::map<Char, node *, Compare> next;
int length = 0;
int surface_count = 0;
int incoming_links = 0;
};
struct deque_entry {
Char character;
node *prefix_surface;
node *suffix_surface;
};
using text_deque =
deque_palindromic_tree_internal::amortized_deque<deque_entry>;
text_deque text_;
std::unique_ptr<node> odd_root_, even_root_;
int distinct_count_ = 0;
node *back_appendable(const Char &character, node *current) {
int n = text_.size();
while (true) {
if (current->length == -1 ||
(current->length < n &&
text_[n - current->length - 1].character == character)) {
return current;
}
node *suffix = current->link;
if (suffix->length == -1 ||
text_[n - suffix->length - 1].character == character) {
return suffix;
}
current = current->quick;
}
}
node *front_appendable(const Char &character, node *current) {
int n = text_.size();
while (true) {
if (current->length == -1 ||
(current->length < n &&
text_[current->length].character == character)) {
return current;
}
node *suffix = current->link;
if (suffix->length == -1 ||
text_[suffix->length].character == character) {
return suffix;
}
current = current->quick;
}
}
static node *transition(node *from, const Char &character) {
auto iterator = from->next.find(character);
assert(iterator != from->next.end());
return iterator->second;
}
public:
deque_palindromic_tree()
: odd_root_(std::make_unique<node>()),
even_root_(std::make_unique<node>()) {
odd_root_->length = -1;
odd_root_->parent = odd_root_->link = odd_root_->quick = odd_root_.get();
even_root_->length = 0;
even_root_->parent = even_root_->link = even_root_->quick = odd_root_.get();
}
deque_palindromic_tree(const deque_palindromic_tree &) = delete;
deque_palindromic_tree &operator=(const deque_palindromic_tree &) = delete;
deque_palindromic_tree(deque_palindromic_tree &&) = delete;
deque_palindromic_tree &operator=(deque_palindromic_tree &&) = delete;
~deque_palindromic_tree() { clear(); }
int size() const { return text_.size(); }
bool empty() const { return text_.empty(); }
int distinct_palindromes() const { return distinct_count_; }
int longest_prefix_palindrome() const {
return empty() ? 0 : text_.front().prefix_surface->length;
}
int longest_suffix_palindrome() const {
return empty() ? 0 : text_.back().suffix_surface->length;
}
void push_back(const Char &character) {
node *parent =
empty() ? odd_root_.get()
: back_appendable(character, text_.back().suffix_surface);
int n = size();
node *created = nullptr;
node *suffix = even_root_.get();
auto existing = parent->next.find(character);
if (existing == parent->next.end()) {
created = new node();
created->parent = parent;
created->length = parent->length + 2;
if (parent != odd_root_.get()) {
node *suffix_parent = back_appendable(character, parent->link);
suffix = transition(suffix_parent, character);
}
created->link = suffix;
suffix->incoming_links++;
text_.push_back({character, even_root_.get(), even_root_.get()});
n++;
if (suffix->link != odd_root_.get() &&
text_[n - suffix->length - 1].character ==
text_[n - suffix->link->length - 1].character) {
created->quick = suffix->quick;
} else {
created->quick = suffix->link;
}
parent->next.emplace(character, created);
distinct_count_++;
} else {
text_.push_back({character, even_root_.get(), even_root_.get()});
n++;
created = existing->second;
suffix = created->link;
}
text_[n - 1].suffix_surface = created;
text_[n - created->length].prefix_surface = created;
if (suffix->length >= 1 &&
text_[n - created->length + suffix->length - 1].suffix_surface ==
suffix) {
text_[n - created->length + suffix->length - 1].suffix_surface =
even_root_.get();
}
created->surface_count++;
}
void push_front(const Char &character) {
node *parent =
empty() ? odd_root_.get()
: front_appendable(character, text_.front().prefix_surface);
node *created = nullptr;
node *suffix = even_root_.get();
auto existing = parent->next.find(character);
if (existing == parent->next.end()) {
created = new node();
created->parent = parent;
created->length = parent->length + 2;
if (parent != odd_root_.get()) {
node *suffix_parent = front_appendable(character, parent->link);
suffix = transition(suffix_parent, character);
}
created->link = suffix;
suffix->incoming_links++;
text_.push_front({character, even_root_.get(), even_root_.get()});
if (suffix->link != odd_root_.get() &&
text_[suffix->length].character ==
text_[suffix->link->length].character) {
created->quick = suffix->quick;
} else {
created->quick = suffix->link;
}
parent->next.emplace(character, created);
distinct_count_++;
} else {
text_.push_front({character, even_root_.get(), even_root_.get()});
created = existing->second;
suffix = created->link;
}
text_[0].prefix_surface = created;
text_[created->length - 1].suffix_surface = created;
if (suffix->length >= 1 &&
text_[created->length - suffix->length].prefix_surface == suffix) {
text_[created->length - suffix->length].prefix_surface = even_root_.get();
}
created->surface_count++;
}
void pop_back() {
assert(!empty());
node *removed = text_.back().suffix_surface;
Char character = text_.back().character;
node *suffix = removed->link;
int n = size();
if (removed->length >= 2 &&
text_[n - removed->length + suffix->length - 1].suffix_surface->length <
suffix->length) {
text_[n - removed->length + suffix->length - 1].suffix_surface = suffix;
text_[n - removed->length].prefix_surface = suffix;
} else {
text_[n - removed->length].prefix_surface = even_root_.get();
}
removed->surface_count--;
if (removed->incoming_links == 0 && removed->surface_count == 0) {
std::size_t erased = removed->parent->next.erase(character);
assert(erased == 1);
suffix->incoming_links--;
delete removed;
distinct_count_--;
}
text_.pop_back();
}
void pop_front() {
assert(!empty());
node *removed = text_.front().prefix_surface;
Char character = text_.front().character;
node *suffix = removed->link;
if (removed->length >= 2 &&
text_[removed->length - suffix->length].prefix_surface->length <
suffix->length) {
text_[removed->length - suffix->length].prefix_surface = suffix;
text_[removed->length - 1].suffix_surface = suffix;
} else {
text_[removed->length - 1].suffix_surface = even_root_.get();
}
removed->surface_count--;
if (removed->incoming_links == 0 && removed->surface_count == 0) {
std::size_t erased = removed->parent->next.erase(character);
assert(erased == 1);
suffix->incoming_links--;
delete removed;
distinct_count_--;
}
text_.pop_front();
}
void clear() {
while (!empty()) {
pop_back();
}
}
};
} // namespace noya
#endif // NOYA_DEQUE_PALINDROMIC_TREE_HPP
#include <algorithm>
#include <cassert>
#include <cstddef>
#include <functional>
#include <iterator>
#include <map>
#include <memory>
#include <utility>
#include <vector>
/// @complexity Time: push O(log n + log sigma) worst case, pop O(log sigma)
/// amortized, and query O(1). Space: O(n), where n is the current length and
/// sigma is the number of distinct character values.
namespace noya {
namespace deque_palindromic_tree_internal {
template <class T> class amortized_deque {
std::vector<T> left_, right_;
static void move_half(std::vector<T> &target, std::vector<T> &source) {
assert(target.empty() && !source.empty());
std::size_t moved = (source.size() + 1) / 2;
std::move(source.rend() - moved, source.rend(), std::back_inserter(target));
source.erase(source.begin(), source.begin() + moved);
}
public:
int size() const { return int(left_.size() + right_.size()); }
bool empty() const { return left_.empty() && right_.empty(); }
T &operator[](int index) {
assert(0 <= index && index < size());
return index < int(left_.size())
? left_[left_.size() - 1 - std::size_t(index)]
: right_[std::size_t(index) - left_.size()];
}
const T &operator[](int index) const {
assert(0 <= index && index < size());
return index < int(left_.size())
? left_[left_.size() - 1 - std::size_t(index)]
: right_[std::size_t(index) - left_.size()];
}
T &front() { return left_.empty() ? right_.front() : left_.back(); }
const T &front() const {
return left_.empty() ? right_.front() : left_.back();
}
T &back() { return right_.empty() ? left_.front() : right_.back(); }
const T &back() const {
return right_.empty() ? left_.front() : right_.back();
}
void push_front(const T &value) { left_.push_back(value); }
void push_front(T &&value) { left_.push_back(std::move(value)); }
void push_back(const T &value) { right_.push_back(value); }
void push_back(T &&value) { right_.push_back(std::move(value)); }
void pop_front() {
assert(!empty());
if (left_.empty()) {
move_half(left_, right_);
}
left_.pop_back();
}
void pop_back() {
assert(!empty());
if (right_.empty()) {
move_half(right_, left_);
}
right_.pop_back();
}
};
} // namespace deque_palindromic_tree_internal
/// @brief Maintain all distinct palindromic substrings under pushes and pops
/// at both ends. Every active palindrome is a node with a suffix link, while
/// each text position stores the longest palindrome beginning or ending there.
/// A quick link skips suffix-link runs whose next extension character is the
/// same, so a new extendable boundary palindrome is found logarithmically.
/// Surface counters and incoming suffix-link counters identify a node exactly
/// when its last occurrence disappears, allowing an end deletion to undo only
/// local certificates. Two reversed vectors provide amortized constant-time
/// deque rebalancing while retaining indexed character access.
template <class Char = int, class Compare = std::less<Char>>
class deque_palindromic_tree {
struct node {
node *parent = nullptr;
node *link = nullptr;
node *quick = nullptr;
std::map<Char, node *, Compare> next;
int length = 0;
int surface_count = 0;
int incoming_links = 0;
};
struct deque_entry {
Char character;
node *prefix_surface;
node *suffix_surface;
};
using text_deque =
deque_palindromic_tree_internal::amortized_deque<deque_entry>;
text_deque text_;
std::unique_ptr<node> odd_root_, even_root_;
int distinct_count_ = 0;
node *back_appendable(const Char &character, node *current) {
int n = text_.size();
while (true) {
if (current->length == -1 ||
(current->length < n &&
text_[n - current->length - 1].character == character)) {
return current;
}
node *suffix = current->link;
if (suffix->length == -1 ||
text_[n - suffix->length - 1].character == character) {
return suffix;
}
current = current->quick;
}
}
node *front_appendable(const Char &character, node *current) {
int n = text_.size();
while (true) {
if (current->length == -1 ||
(current->length < n &&
text_[current->length].character == character)) {
return current;
}
node *suffix = current->link;
if (suffix->length == -1 ||
text_[suffix->length].character == character) {
return suffix;
}
current = current->quick;
}
}
static node *transition(node *from, const Char &character) {
auto iterator = from->next.find(character);
assert(iterator != from->next.end());
return iterator->second;
}
public:
deque_palindromic_tree()
: odd_root_(std::make_unique<node>()),
even_root_(std::make_unique<node>()) {
odd_root_->length = -1;
odd_root_->parent = odd_root_->link = odd_root_->quick = odd_root_.get();
even_root_->length = 0;
even_root_->parent = even_root_->link = even_root_->quick = odd_root_.get();
}
deque_palindromic_tree(const deque_palindromic_tree &) = delete;
deque_palindromic_tree &operator=(const deque_palindromic_tree &) = delete;
deque_palindromic_tree(deque_palindromic_tree &&) = delete;
deque_palindromic_tree &operator=(deque_palindromic_tree &&) = delete;
~deque_palindromic_tree() { clear(); }
int size() const { return text_.size(); }
bool empty() const { return text_.empty(); }
int distinct_palindromes() const { return distinct_count_; }
int longest_prefix_palindrome() const {
return empty() ? 0 : text_.front().prefix_surface->length;
}
int longest_suffix_palindrome() const {
return empty() ? 0 : text_.back().suffix_surface->length;
}
void push_back(const Char &character) {
node *parent =
empty() ? odd_root_.get()
: back_appendable(character, text_.back().suffix_surface);
int n = size();
node *created = nullptr;
node *suffix = even_root_.get();
auto existing = parent->next.find(character);
if (existing == parent->next.end()) {
created = new node();
created->parent = parent;
created->length = parent->length + 2;
if (parent != odd_root_.get()) {
node *suffix_parent = back_appendable(character, parent->link);
suffix = transition(suffix_parent, character);
}
created->link = suffix;
suffix->incoming_links++;
text_.push_back({character, even_root_.get(), even_root_.get()});
n++;
if (suffix->link != odd_root_.get() &&
text_[n - suffix->length - 1].character ==
text_[n - suffix->link->length - 1].character) {
created->quick = suffix->quick;
} else {
created->quick = suffix->link;
}
parent->next.emplace(character, created);
distinct_count_++;
} else {
text_.push_back({character, even_root_.get(), even_root_.get()});
n++;
created = existing->second;
suffix = created->link;
}
text_[n - 1].suffix_surface = created;
text_[n - created->length].prefix_surface = created;
if (suffix->length >= 1 &&
text_[n - created->length + suffix->length - 1].suffix_surface ==
suffix) {
text_[n - created->length + suffix->length - 1].suffix_surface =
even_root_.get();
}
created->surface_count++;
}
void push_front(const Char &character) {
node *parent =
empty() ? odd_root_.get()
: front_appendable(character, text_.front().prefix_surface);
node *created = nullptr;
node *suffix = even_root_.get();
auto existing = parent->next.find(character);
if (existing == parent->next.end()) {
created = new node();
created->parent = parent;
created->length = parent->length + 2;
if (parent != odd_root_.get()) {
node *suffix_parent = front_appendable(character, parent->link);
suffix = transition(suffix_parent, character);
}
created->link = suffix;
suffix->incoming_links++;
text_.push_front({character, even_root_.get(), even_root_.get()});
if (suffix->link != odd_root_.get() &&
text_[suffix->length].character ==
text_[suffix->link->length].character) {
created->quick = suffix->quick;
} else {
created->quick = suffix->link;
}
parent->next.emplace(character, created);
distinct_count_++;
} else {
text_.push_front({character, even_root_.get(), even_root_.get()});
created = existing->second;
suffix = created->link;
}
text_[0].prefix_surface = created;
text_[created->length - 1].suffix_surface = created;
if (suffix->length >= 1 &&
text_[created->length - suffix->length].prefix_surface == suffix) {
text_[created->length - suffix->length].prefix_surface = even_root_.get();
}
created->surface_count++;
}
void pop_back() {
assert(!empty());
node *removed = text_.back().suffix_surface;
Char character = text_.back().character;
node *suffix = removed->link;
int n = size();
if (removed->length >= 2 &&
text_[n - removed->length + suffix->length - 1].suffix_surface->length <
suffix->length) {
text_[n - removed->length + suffix->length - 1].suffix_surface = suffix;
text_[n - removed->length].prefix_surface = suffix;
} else {
text_[n - removed->length].prefix_surface = even_root_.get();
}
removed->surface_count--;
if (removed->incoming_links == 0 && removed->surface_count == 0) {
std::size_t erased = removed->parent->next.erase(character);
assert(erased == 1);
suffix->incoming_links--;
delete removed;
distinct_count_--;
}
text_.pop_back();
}
void pop_front() {
assert(!empty());
node *removed = text_.front().prefix_surface;
Char character = text_.front().character;
node *suffix = removed->link;
if (removed->length >= 2 &&
text_[removed->length - suffix->length].prefix_surface->length <
suffix->length) {
text_[removed->length - suffix->length].prefix_surface = suffix;
text_[removed->length - 1].suffix_surface = suffix;
} else {
text_[removed->length - 1].suffix_surface = even_root_.get();
}
removed->surface_count--;
if (removed->incoming_links == 0 && removed->surface_count == 0) {
std::size_t erased = removed->parent->next.erase(character);
assert(erased == 1);
suffix->incoming_links--;
delete removed;
distinct_count_--;
}
text_.pop_front();
}
void clear() {
while (!empty()) {
pop_back();
}
}
};
} // namespace noya