Trie
(string/trie.hpp)

View this file on GitHub
Last update: 2026-06-22 15:33:45+09:00
Include: #include "string/trie.hpp"

Overview

m1une::string::Trie is a multiset of strings represented by a prefix tree. It supports duplicate insertion, deletion, exact lookup, counting strings with a given prefix, and enumerating stored strings that are prefixes of a query.

Nodes are stored in one contiguous vector. The alphabet must be a contiguous range of character codes, making transitions constant-time without maps or per-edge allocations.

Template Parameters

AlphabetSize: Number of symbols in the alphabet. Defaults to 26.
FirstCharacter: Character code corresponding to transition 0. Defaults to 'a'.

The default Trie<> accepts lowercase English letters. For decimal digits, use Trie<10, '0'>.

Methods are generic over iterable sequences whose symbols can be converted to integers, including std::string, std::string_view, and character vectors. Every symbol must lie in the configured alphabet.

Methods

Let $L$ be the sequence length.

Method	Description	Complexity
`int size()`	Returns the number of stored strings including duplicates.	$O(1)$
`int distinct_size()`	Returns the number of distinct stored strings.	$O(1)$
`bool empty()`	Returns whether no strings are stored.	$O(1)$
`node_id root()`	Returns the root node handle.	$O(1)$
`node_id find(sequence)`	Returns the node reached by an active path, or `null_node` if it is absent.	$O(L)$
`const Node& node(node_id id)`	Returns a read-only view of a node.	$O(1)$
`size_t node_count()`	Returns allocated nodes, including the root.	$O(1)$
`void reserve(size_t n)`	Reserves storage for approximately `n` nodes.	$O(K)$
`void clear()`	Removes all strings.	$O(K)$
`node_id insert(sequence, int multiplicity = 1)`	Inserts copies of `sequence` and returns its endpoint node handle.	$O(L)$
`int count(sequence)`	Returns the sequence multiplicity.	$O(L)$
`bool contains(sequence)`	Returns whether the sequence is stored.	$O(L)$
`int prefix_count(prefix)`	Counts stored strings beginning with `prefix`, including duplicates.	$O(L)$
`bool starts_with(prefix)`	Returns whether any stored string begins with `prefix`.	$O(L)$
`bool erase_one(sequence)`, `bool erase(sequence)`	Erases one copy and reports success.	$O(L)$
`int erase_all(sequence)`	Erases all copies and returns the number erased.	$O(L)$
`void for_each_prefix(sequence, callback)`	Calls `callback(length, multiplicity)` for each stored string that is a prefix of `sequence`.	$O(L)$
`int longest_prefix(sequence)`	Returns the longest stored prefix length, or `-1` if none exists.	$O(L)$

Here $K$ is the allocated node count. Erasing does not reclaim nodes; clear releases all logical contents at once.

node_id is an integer handle and null_node is its invalid value. A Node exposes child, subtree_count, and terminal_count. Node handles remain valid across insertions and erasures, so they can also index user-owned metadata. clear() invalidates every old handle except the root. References returned by node() may be invalidated by insertion, reserve(), or clear(); keep the handle rather than the reference.

The empty string is supported. When stored, it is reported by for_each_prefix with length 0, and prefix_count("") equals size().

Example

#include "string/trie.hpp"

#include <iostream>
#include <string>

int main() {
    m1une::string::Trie<> trie;
    trie.insert(std::string("app"));
    trie.insert(std::string("apple"));
    trie.insert(std::string("app"));

    std::cout << trie.count(std::string("app")) << "\n";       // 2
    std::cout << trie.prefix_count(std::string("app")) << "\n"; // 3
    std::cout << trie.longest_prefix(std::string("apples")) << "\n"; // 5
}

Required by

String Algorithms Bundle (string/all.hpp)

Verified with

Code

#ifndef M1UNE_STRING_TRIE_HPP
#define M1UNE_STRING_TRIE_HPP 1

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

namespace m1une {
namespace string {

// A multiset trie for a contiguous character alphabet.
template <int AlphabetSize = 26, int FirstCharacter = 'a'>
struct Trie {
    static_assert(0 < AlphabetSize);

    using node_id = int;
    static constexpr node_id null_node = -1;

    struct Node {
        std::array<node_id, AlphabetSize> child;
        int subtree_count;
        int terminal_count;

        Node() : subtree_count(0), terminal_count(0) {
            child.fill(null_node);
        }
    };

   private:
    std::vector<Node> _nodes;
    int _distinct_size;

    template <class Symbol>
    static int symbol_index(const Symbol& symbol) {
        int index = int(symbol) - FirstCharacter;
        assert(0 <= index && index < AlphabetSize);
        return index;
    }

    node_id new_node() {
        assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        _nodes.emplace_back();
        return int(_nodes.size()) - 1;
    }

    template <class Sequence>
    node_id find_node(const Sequence& sequence) const {
        node_id node = 0;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child[symbol_index(symbol)];
            if (node == null_node || _nodes[node].subtree_count == 0) {
                return null_node;
            }
        }
        return node;
    }

   public:
    Trie() : _nodes(1), _distinct_size(0) {}

    int size() const {
        return _nodes[0].subtree_count;
    }

    int distinct_size() const {
        return _distinct_size;
    }

    bool empty() const {
        return size() == 0;
    }

    node_id root() const {
        return 0;
    }

    const Node& node(node_id id) const {
        assert(0 <= id && std::size_t(id) < _nodes.size());
        return _nodes[id];
    }

    template <class Sequence>
    node_id find(const Sequence& sequence) const {
        return find_node(sequence);
    }

    std::size_t node_count() const {
        return _nodes.size();
    }

    void reserve(std::size_t node_capacity) {
        _nodes.reserve(node_capacity);
    }

    void clear() {
        _nodes.clear();
        _nodes.emplace_back();
        _distinct_size = 0;
    }

    template <class Sequence>
    node_id insert(const Sequence& sequence, int multiplicity = 1) {
        assert(0 < multiplicity);
        node_id node = 0;
        _nodes[node].subtree_count += multiplicity;
        for (const auto& symbol : sequence) {
            int index = symbol_index(symbol);
            node_id child = _nodes[node].child[index];
            if (child == null_node) {
                child = new_node();
                _nodes[node].child[index] = child;
            }
            node = child;
            _nodes[node].subtree_count += multiplicity;
        }
        if (_nodes[node].terminal_count == 0) _distinct_size++;
        _nodes[node].terminal_count += multiplicity;
        return node;
    }

    template <class Sequence>
    int count(const Sequence& sequence) const {
        node_id node = find_node(sequence);
        return node == null_node ? 0 : _nodes[node].terminal_count;
    }

    template <class Sequence>
    bool contains(const Sequence& sequence) const {
        return count(sequence) != 0;
    }

    // Returns the number of stored strings beginning with prefix.
    template <class Sequence>
    int prefix_count(const Sequence& prefix) const {
        node_id node = find_node(prefix);
        return node == null_node ? 0 : _nodes[node].subtree_count;
    }

    template <class Sequence>
    bool starts_with(const Sequence& prefix) const {
        return prefix_count(prefix) != 0;
    }

    template <class Sequence>
    bool erase_one(const Sequence& sequence) {
        node_id terminal = find_node(sequence);
        if (terminal == null_node || _nodes[terminal].terminal_count == 0) {
            return false;
        }

        int node = 0;
        _nodes[node].subtree_count--;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child[symbol_index(symbol)];
            _nodes[node].subtree_count--;
        }
        _nodes[node].terminal_count--;
        if (_nodes[node].terminal_count == 0) _distinct_size--;
        return true;
    }

    template <class Sequence>
    bool erase(const Sequence& sequence) {
        return erase_one(sequence);
    }

    template <class Sequence>
    int erase_all(const Sequence& sequence) {
        int multiplicity = count(sequence);
        if (multiplicity == 0) return 0;

        int node = 0;
        _nodes[node].subtree_count -= multiplicity;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child[symbol_index(symbol)];
            _nodes[node].subtree_count -= multiplicity;
        }
        _nodes[node].terminal_count = 0;
        _distinct_size--;
        return multiplicity;
    }

    // Calls callback(length, multiplicity) for every stored prefix.
    // The empty prefix is reported with length 0 when it is stored.
    template <class Sequence, class Callback>
    void for_each_prefix(const Sequence& sequence, Callback callback) const {
        int node = 0;
        if (_nodes[node].terminal_count != 0) {
            callback(0, _nodes[node].terminal_count);
        }

        int length = 0;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child[symbol_index(symbol)];
            if (node == null_node || _nodes[node].subtree_count == 0) return;
            length++;
            if (_nodes[node].terminal_count != 0) {
                callback(length, _nodes[node].terminal_count);
            }
        }
    }

    // Returns the length of the longest stored string that is a prefix.
    // Returns -1 when no stored prefix exists.
    template <class Sequence>
    int longest_prefix(const Sequence& sequence) const {
        int result = _nodes[0].terminal_count == 0 ? -1 : 0;
        for_each_prefix(sequence, [&result](int length, int) {
            result = length;
        });
        return result;
    }
};

}  // namespace string
}  // namespace m1une

#endif  // M1UNE_STRING_TRIE_HPP

#line 1 "string/trie.hpp"



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

namespace m1une {
namespace string {

// A multiset trie for a contiguous character alphabet.
template <int AlphabetSize = 26, int FirstCharacter = 'a'>
struct Trie {
    static_assert(0 < AlphabetSize);

    using node_id = int;
    static constexpr node_id null_node = -1;

    struct Node {
        std::array<node_id, AlphabetSize> child;
        int subtree_count;
        int terminal_count;

        Node() : subtree_count(0), terminal_count(0) {
            child.fill(null_node);
        }
    };

   private:
    std::vector<Node> _nodes;
    int _distinct_size;

    template <class Symbol>
    static int symbol_index(const Symbol& symbol) {
        int index = int(symbol) - FirstCharacter;
        assert(0 <= index && index < AlphabetSize);
        return index;
    }

    node_id new_node() {
        assert(_nodes.size() < std::size_t(std::numeric_limits<int>::max()));
        _nodes.emplace_back();
        return int(_nodes.size()) - 1;
    }

    template <class Sequence>
    node_id find_node(const Sequence& sequence) const {
        node_id node = 0;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child[symbol_index(symbol)];
            if (node == null_node || _nodes[node].subtree_count == 0) {
                return null_node;
            }
        }
        return node;
    }

   public:
    Trie() : _nodes(1), _distinct_size(0) {}

    int size() const {
        return _nodes[0].subtree_count;
    }

    int distinct_size() const {
        return _distinct_size;
    }

    bool empty() const {
        return size() == 0;
    }

    node_id root() const {
        return 0;
    }

    const Node& node(node_id id) const {
        assert(0 <= id && std::size_t(id) < _nodes.size());
        return _nodes[id];
    }

    template <class Sequence>
    node_id find(const Sequence& sequence) const {
        return find_node(sequence);
    }

    std::size_t node_count() const {
        return _nodes.size();
    }

    void reserve(std::size_t node_capacity) {
        _nodes.reserve(node_capacity);
    }

    void clear() {
        _nodes.clear();
        _nodes.emplace_back();
        _distinct_size = 0;
    }

    template <class Sequence>
    node_id insert(const Sequence& sequence, int multiplicity = 1) {
        assert(0 < multiplicity);
        node_id node = 0;
        _nodes[node].subtree_count += multiplicity;
        for (const auto& symbol : sequence) {
            int index = symbol_index(symbol);
            node_id child = _nodes[node].child[index];
            if (child == null_node) {
                child = new_node();
                _nodes[node].child[index] = child;
            }
            node = child;
            _nodes[node].subtree_count += multiplicity;
        }
        if (_nodes[node].terminal_count == 0) _distinct_size++;
        _nodes[node].terminal_count += multiplicity;
        return node;
    }

    template <class Sequence>
    int count(const Sequence& sequence) const {
        node_id node = find_node(sequence);
        return node == null_node ? 0 : _nodes[node].terminal_count;
    }

    template <class Sequence>
    bool contains(const Sequence& sequence) const {
        return count(sequence) != 0;
    }

    // Returns the number of stored strings beginning with prefix.
    template <class Sequence>
    int prefix_count(const Sequence& prefix) const {
        node_id node = find_node(prefix);
        return node == null_node ? 0 : _nodes[node].subtree_count;
    }

    template <class Sequence>
    bool starts_with(const Sequence& prefix) const {
        return prefix_count(prefix) != 0;
    }

    template <class Sequence>
    bool erase_one(const Sequence& sequence) {
        node_id terminal = find_node(sequence);
        if (terminal == null_node || _nodes[terminal].terminal_count == 0) {
            return false;
        }

        int node = 0;
        _nodes[node].subtree_count--;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child[symbol_index(symbol)];
            _nodes[node].subtree_count--;
        }
        _nodes[node].terminal_count--;
        if (_nodes[node].terminal_count == 0) _distinct_size--;
        return true;
    }

    template <class Sequence>
    bool erase(const Sequence& sequence) {
        return erase_one(sequence);
    }

    template <class Sequence>
    int erase_all(const Sequence& sequence) {
        int multiplicity = count(sequence);
        if (multiplicity == 0) return 0;

        int node = 0;
        _nodes[node].subtree_count -= multiplicity;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child[symbol_index(symbol)];
            _nodes[node].subtree_count -= multiplicity;
        }
        _nodes[node].terminal_count = 0;
        _distinct_size--;
        return multiplicity;
    }

    // Calls callback(length, multiplicity) for every stored prefix.
    // The empty prefix is reported with length 0 when it is stored.
    template <class Sequence, class Callback>
    void for_each_prefix(const Sequence& sequence, Callback callback) const {
        int node = 0;
        if (_nodes[node].terminal_count != 0) {
            callback(0, _nodes[node].terminal_count);
        }

        int length = 0;
        for (const auto& symbol : sequence) {
            node = _nodes[node].child[symbol_index(symbol)];
            if (node == null_node || _nodes[node].subtree_count == 0) return;
            length++;
            if (_nodes[node].terminal_count != 0) {
                callback(length, _nodes[node].terminal_count);
            }
        }
    }

    // Returns the length of the longest stored string that is a prefix.
    // Returns -1 when no stored prefix exists.
    template <class Sequence>
    int longest_prefix(const Sequence& sequence) const {
        int result = _nodes[0].terminal_count == 0 ? -1 : 0;
        for_each_prefix(sequence, [&result](int length, int) {
            result = length;
        });
        return result;
    }
};

}  // namespace string
}  // namespace m1une

m1une's library

This documentation is automatically generated by online-judge-tools/verification-helper

Trie
(string/trie.hpp)

Overview

Template Parameters

Methods

Example

Required by

Verified with

Code

Trie (string/trie.hpp)

Overview

Template Parameters

Methods

Example

Required by

Verified with

Code

Trie
(string/trie.hpp)