競プロノート

Appearance

Trie木 ​

文字列を木構造で管理し、文字列検索や接頭辞検索を高速に行うデータ構造。

特徴 ​

項目内容
用途文字列集合の管理・接頭辞検索
挿入平均 O(L)
完全一致検索平均 O(L)
接頭辞検索平均 O(L)
空間計算量O(登録した文字列の総文字数)

Lは操作対象の文字列長。計算量はハッシュ表の操作が平均O(1)の場合。

実装 ​

cpp

#pragma once
#include <string>
#include <unordered_map>
#include <vector>

struct Trie {
    struct Node {
        std::unordered_map<char, int> nxt;
        int pass = 0;  // このノードを通過する文字列の数
        int term = 0;  // このノードで終端となる文字列の数
    };

    std::vector<Node> t;
    Trie() { t.emplace_back(); }

    // 文字列を挿入し、終端ノードの番号を返す
    int insert(const std::string& s) {
        int v = 0;
        t[v].pass++;
        for (char c : s) {
            auto it = t[v].nxt.find(c);
            if (it == t[v].nxt.end()) {
                int nv = (int)t.size();
                t[v].nxt.emplace(c, nv);
                t.emplace_back();
                v = nv;
            } else {
                v = it->second;
            }
            t[v].pass++;
        }
        t[v].term++;
        return v;
    }

    // 文字列に対応するパスの終端ノードを返す（なければ-1）
    int find_node(const std::string& s) const {
        int v = 0;
        for (char c : s) {
            auto it = t[v].nxt.find(c);
            if (it == t[v].nxt.end()) return -1;
            v = it->second;
        }
        return v;
    }

    // 完全一致する文字列が存在するか
    bool contains(const std::string& s) const {
        int v = find_node(s);
        return v != -1 && t[v].term > 0;
    }

    // 接頭辞pを持つ登録済み文字列が存在するか
    bool starts_with(const std::string& p) const {
        int v = find_node(p);
        return v != -1 && t[v].pass > 0;
    }

    // 接頭辞pを持つ文字列の数
    int count_prefix(const std::string& p) const {
        int v = find_node(p);
        return v == -1 ? 0 : t[v].pass;
    }

    // 完全一致する文字列の数
    int count_word(const std::string& s) const {
        int v = find_node(s);
        return v == -1 ? 0 : t[v].term;
    }
};

使用例 ​

cpp
Trie tr;
tr.insert("apple");
tr.insert("app");
tr.insert("app");

cout << tr.contains("app") << "\n";       // 1
cout << tr.count_word("app") << "\n";     // 2
cout << tr.starts_with("ap") << "\n";     // 1
cout << tr.count_prefix("app") << "\n";  // 3

主な操作 ​

メソッド機能
insert(s)文字列を挿入し、終端ノード番号を返す
find_node(s)文字列に対応するパスの終端ノードを返す
contains(s)完全一致する文字列が存在するか
starts_with(p)接頭辞pを持つ文字列が存在するか
count_prefix(p)接頭辞pを持つ文字列の数
count_word(s)完全一致する文字列の数

注意点 ​

  • 同じ文字列を複数回挿入できる。
  • pass はそのノードを通る文字列数、term はそのノードで終わる文字列数。
  • find_node(s) != -1 は、文字列sが登録済みであることを意味しない。完全一致には contains(s) を使う。
  • count_prefix("") は挿入した文字列の総数を返す。
  • 現在の実装は文字列の削除に対応していない。
  • unordered_map を各ノードに持つため、メモリ消費が大きくなりやすい。
  • 英小文字のみなら array<int, 26> などで遷移を管理する方法もある。
  • char 単位の実装なので、UTF-8の日本語文字を1文字単位で扱う用途にはそのままでは適さない。

関連 ​

  • 文字列検索
  • Z Algorithm
  • Aho-Corasick法