Eertree
(string/eertree.hpp)

• View this file on GitHub
• Last update: 2026-06-23 11:42:02+09:00
• Include: #include "string/eertree.hpp"

Overview

Eertree is a palindromic tree. It stores every distinct nonempty palindrome appearing in an incrementally built sequence.

Appending one symbol takes amortized O(1) time. The complete structure uses at most N + 2 nodes for a text of length N: one node per distinct palindrome, plus roots representing lengths zero and minus one.

The implementation uses fixed transition arrays and a contiguous alphabet, matching Trie and AhoCorasick. The default alphabet is lowercase English letters.

PalindromicTree is an alias for Eertree.

Template Parameters

• AlphabetSize: number of symbols, default 26.
• FirstCharacter: character code mapped to transition zero, default 'a'.

For example, Eertree<10, '0'> accepts decimal digits.

Node Fields

Field	Meaning
next[c]	Palindrome obtained by adding symbol c to both ends, or null_node.
suffix_link	Longest proper palindromic suffix.
series_link	Nearest suffix-link ancestor having a different diff.
length	Palindrome length.
diff	length - length[suffix_link], used in series-link DP.
suffix_count	Number of nonempty palindromic suffixes of this palindrome.
first_end	Exclusive end position of its first occurrence.
suffix_occurrences	Number of prefixes for which this node was the longest palindromic suffix.

occurrence_counts() propagates suffix_occurrences through suffix links and returns the total number of occurrences of each palindrome.

Roots and Node IDs

• even_root has node id zero and length zero.
• odd_root has node id one and length minus one.
• Real palindrome nodes begin at id two.

size() counts only real palindrome nodes, while node_count() includes both roots.

Methods

Let D be the number of distinct palindromes.

Method	Description	Complexity
Eertree()	Creates an empty tree.	O(1)
Eertree(sequence)	Builds from a sequence.	O(N) amortized
int size() const	Returns D.	O(1)
bool empty() const	Returns whether D is zero.	O(1)
int node_count() const	Returns D + 2.	O(1)
int text_length() const	Returns the appended sequence length.	O(1)
node_id last() const	Returns the longest palindromic suffix node.	O(1)
int longest_suffix_length() const	Returns its length.	O(1)
const Node& node(id) const	Returns node metadata.	O(1)
const vector<Node>& nodes() const	Returns all nodes.	O(1)
node_id longest_suffix_node(prefix_length) const	Returns the longest suffix of that nonempty prefix.	O(1)
const vector<node_id>& longest_suffix_nodes() const	Returns this node for every prefix.	O(1)
void for_each_suffix(id, callback) const	Enumerates nonempty palindromic suffix nodes beginning at id.	O(P)
void for_each_suffix(callback) const	Enumerates suffixes of the complete current text.	O(P)
void reserve(capacity)	Reserves text and node storage.	O(D) if reallocated
void clear()	Resets to the two roots.	O(D)
node_id add(symbol)	Appends one symbol and returns the new longest suffix.	Amortized O(1)
void build(sequence)	Appends every symbol in the sequence.	Amortized O(N)
vector<long long> occurrence_counts() const	Returns total occurrence counts by node id.	O(D)
pair<int, int> first_occurrence(id) const	Returns its first half-open interval.	O(1)

Here P is the number of reported palindromic suffixes.

Node handles remain valid until clear(). References returned by node() may be invalidated by add, build, reserve, or clear.

Example

#include "string/eertree.hpp"
#include <iostream>
#include <string>

int main() {
    m1une::string::Eertree<> tree(std::string("ababa"));
    std::vector<long long> count = tree.occurrence_counts();

    std::cout << tree.size() << '\n';  // 5
    for (int id = 2; id < tree.node_count(); id++) {
        auto [left, right] = tree.first_occurrence(id);
        std::cout << tree.node(id).length << ' ' << count[id] << ' '
                  << left << ' ' << right << '\n';
    }
}

Required by

• String Algorithms Bundle (string/all.hpp)
• Palindrome Lexicographical Order (string/palindrome_lexicographical_order.hpp)

Verified with

• verify/string/eertree.test.cpp
• verify/string/palindrome_lexicographical_order.test.cpp
• verify/string/string_algorithms.test.cpp

Code

#ifndef M1UNE_STRING_EERTREE_HPP
#define M1UNE_STRING_EERTREE_HPP 1

#include <array>
#include <cassert>
#include <cstddef>
#include <limits>
#include <utility>
#include <vector>

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

#endif  // M1UNE_STRING_EERTREE_HPP

#line 1 "string/eertree.hpp"



#include <array>
#include <cassert>
#include <cstddef>
#include <limits>
#include <utility>
#include <vector>

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

Back to top page