Trie木
(library/string/trie.hpp)

• View this file on GitHub
• Last update: 2026-01-20 20:11:22+09:00
• Include: #include "library/string/trie.hpp"

Trie木

できること

• 接頭辞の木。複数文字列の共通部分をまとめて管理している
• 単語の登録・検索
• 接頭辞（Prefix）検索（指定文字列で始まる単語がいくつ登録されているか）

画像の引用: https://www.geeksforgeeks.org/dsa/trie-insert-and-search/
実装の参考: https://ei1333.github.io/library/structure/trie/trie.hpp

• accept: そのノードで「ちょうど終わる単語のID」を保存
  • “apple”を追加したとき、最後の”e”のノードのacceptにそのIDが入る
• exist: そのノードを「通過した単語の総数」をカウント

（イメージ）”app” (ID:0) と “apple” (ID:1) を入れた状態

Root (nodes[0])
 └── 'a' (nodes[1])
      └── 'p' (nodes[2])
           └── 'p' (nodes[3])  <-- accept: [0], exist: 2
                └── 'l' (nodes[4])
                     └── 'e' (nodes[5]) <-- accept: [1], exist: 1

計算量

• add: $O(\vert S \vert \cdot \sum)$ Sは追加する文字列、 $\sum$ はchar_size
• search: $O(\vert S \vert)$
• count_prefix: $O(\vert S \vert)$

使い方

// 小文字アルファベット 26文字、開始文字 'a' で初期化
Trie<26, 'a'> trie;

// 単語の追加 (IDは任意)
trie.add("apple", 0);
trie.add("app", 1);

// 検索
bool has_apple = trie.search("apple");      // true
bool has_appli = trie.search("appli");      // false (接頭辞としてはあるが単語はない)

// 接頭辞カウント
int cnt = trie.count_prefix("app");         // 2 ("apple", "app")

Required by

• Aho Corasick (library/string/aho_corasick.hpp)
• 文字列複数 統合検索エンジン (library/string/finds.hpp)

Verified with

• Aho Corasickのテスト (tests/string.aho_corasick.test.cpp)
• 文字列複数 統合検索エンジンのテスト (tests/string.finds.test.cpp)

Code

#pragma once
template <int char_size, int margin> struct Trie {
    struct Node {
        vector<int> nxt;
        vector<int> accept; // その地点で終わる単語のIDリスト
        int exist;          // その地点を接頭辞として持つ単語の数
        Node() : nxt(char_size, -1), exist(0) {}
    };
    vector<Node> nodes;
    Trie() { nodes.emplace_back(); }
    int size() const { return (int)nodes.size(); }
    // 単語の追加
    virtual void add(const string &s, int id = -1) {
        int now = 0;
        for (char c : s) {
            int x = c - margin;
            if (nodes[now].nxt[x] == -1) {
                nodes[now].nxt[x] = (int)nodes.size();
                nodes.emplace_back();
            }
            now = nodes[now].nxt[x];
            nodes[now].exist++;
        }
        if (id != -1) nodes[now].accept.push_back(id);
    }
    // 単一の単語の検索 (完全一致)
    bool search(const string &s) const {
        int now = 0;
        for (char c : s) {
            int x = c - margin;
            if (nodes[now].nxt[x] == -1) return false;
            now = nodes[now].nxt[x];
        }
        return !nodes[now].accept.empty();
    }
    // 接頭辞検索：s を接頭辞として持つ単語の数を返す
    int count_prefix(const string &s) const {
        int now = 0;
        for (char c : s) {
            int x = c - margin;
            if (nodes[now].nxt[x] == -1) return 0;
            now = nodes[now].nxt[x];
        }
        return nodes[now].exist;
    }
};

#line 2 "library/string/trie.hpp"
template <int char_size, int margin> struct Trie {
    struct Node {
        vector<int> nxt;
        vector<int> accept; // その地点で終わる単語のIDリスト
        int exist;          // その地点を接頭辞として持つ単語の数
        Node() : nxt(char_size, -1), exist(0) {}
    };
    vector<Node> nodes;
    Trie() { nodes.emplace_back(); }
    int size() const { return (int)nodes.size(); }
    // 単語の追加
    virtual void add(const string &s, int id = -1) {
        int now = 0;
        for (char c : s) {
            int x = c - margin;
            if (nodes[now].nxt[x] == -1) {
                nodes[now].nxt[x] = (int)nodes.size();
                nodes.emplace_back();
            }
            now = nodes[now].nxt[x];
            nodes[now].exist++;
        }
        if (id != -1) nodes[now].accept.push_back(id);
    }
    // 単一の単語の検索 (完全一致)
    bool search(const string &s) const {
        int now = 0;
        for (char c : s) {
            int x = c - margin;
            if (nodes[now].nxt[x] == -1) return false;
            now = nodes[now].nxt[x];
        }
        return !nodes[now].accept.empty();
    }
    // 接頭辞検索：s を接頭辞として持つ単語の数を返す
    int count_prefix(const string &s) const {
        int now = 0;
        for (char c : s) {
            int x = c - margin;
            if (nodes[now].nxt[x] == -1) return 0;
            now = nodes[now].nxt[x];
        }
        return nodes[now].exist;
    }
};

Back to top page