Trie

[Astral-23]

参考 : https://ei1333.github.io/luzhiled/snippets/structure/trie.html

template <int char_size, int mergin> struct Trie {
    struct node_t {
        array<int, char_size> nxt;
        ll cnt;
        set<int> accept;

        node_t() : cnt(0) { nxt.fill(-1); }
    };

    using np = node_t *;
    vector<node_t> nodes;
    int root;
    int nid;

    Trie() : root(0), nid(0) { nodes.push_back(node_t()); }

    int get_nxt(int node_id, int c) {
        if (nodes[node_id].nxt[c] == -1) {
            nodes[node_id].nxt[c] = (int)(nodes.size());
            nodes.push_back(node_t());
        }
        return nodes[node_id].nxt[c];
    }

    template<class T> vector<int> path(T str, bool make) {
        int str_id = 0;
        int node_id = 0;
        vector<int> res;

        while (1) {
            res.push_back(node_id);
            if (str_id == str.size()) {
                break;
            } else {
                int c = str[str_id++] - mergin;
                if(make) node_id = get_nxt(node_id, c);
                else {
                    node_id = nodes[node_id].nxt[c];
                    if(node_id == -1) break;
                }
            }
        }
        return std::move(res);
    }

    template <class T> int insert(T str) {
        auto ns = path(str, true);
        int id = nid++;
        for(auto node_id : ns) {
            ++nodes[node_id].cnt;
        }
        nodes[ns.back()].accept.insert(id);
        return id;
    }

    template <class T, class F> void query(T str, F f) {
        auto ns = path(str, false);
        for(auto node_id : ns) {
            for(int id : nodes[node_id].accept) f(id);
        }
        return;
    }

    template <class T> void erase(T str, int id) {
        auto ns = path(str, true);
        for(auto node_id : ns) {
            --nodes[node_id].cnt;
        }
        nodes[ns.back()].accept.erase(id);
    }

    template<class T> vector<int> count(T str, bool pref) {
        vector<int> res(str.size(), 0);
        auto ns = path(str, false);
        for(int i = 1; i < int(ns.size()); i++) {
            if(pref) res[i-1] = nodes[ns[i]].cnt;
            else res[i-1] = nodes[ns[i]].accept.size();
        }
        return res;
    }

    int size() {
        return nodes[root].cnt;
    }

    ll dfs(ll node_id = 0) {
        if(node_id == -1) return 0;
        ll res = nodes[node_id].cnt * (nodes[node_id].cnt - 1) / 2;
        if(node_id == 0) res = 0;
        for(int i = 0; i < char_size; i++) {
           res += dfs(nodes[node_id].nxt[i]);
        }
        return res;

    }
};

[Astral-23]

verified : https://atcoder.jp/contests/tenka1-2016-final/submissions/55591711 文字列の集合がある時、その集合にクエリを飛ばしたい... な問題? 或いは、文字列を1ずつ伸ばしていく処理を高速に行う...問題。 : https://atcoder.jp/contests/abc353/tasks/abc353_e 文字列の集合がある時、全てのペア(i, j)について...な問題

[Astral-23]

概要

文字の種類数が小さい文字列・数列に対するTrie

コンストラクタ

Trie<int char_size, int mergin>()... [mergin, mergin + char_size) の範囲の文字を扱うTrie木を作る。 $O(1)$

関数

以下、操作の過程で管理している整数xが、0でない桁を最大でn桁保持したとする。

• template <class T> int insert(T str) ... 文字列strを $1$ つ挿入。

  • 計算量 $O(|str| + \log挿入回数)$
  • 戻り値 : 文字列strに割り振られたid。なお、これは"何回目の挿入であるか(0-origin)"に対応する。
  • 備考 : 任意個数挿入するような実装にもできる。その場合、accept(その文字列となるようなindexの集合)が意味の無い値になる。

• template <class T> void erase(T str, int id)... idが割り振られた文字列strを削除する。

  • 計算量 $O(|str| + \log挿入回数)$
  • 備考
    • acceptが壊れる事を許容するなら、idは任意の値で良い。
    • not verified

• template<class T> vector<int> count(T str, bool pref)...文字列strに対し、 res[i] := strの[0, i] に対応する部分文字列が、trieに何個存在するか　を返す。

  • pref = true ... カウントする文字列の対象として、挿入された文字列のprefixも含む
  • pref = false ... カウントする文字列は、挿入された文字列のみである。
  • 計算量 $O(|str|)$
  • 備考
    • not verified

• template <class T, class F> void query(T str, F f)...trie内でstrを探索する過程で訪れる全てのノードについて、そのノードを終点とする文字列に対し、関数 $f$ を呼ぶ。

  • $f$ は、引数として int を $1$ つ受け取らなければならない。これには、文字列のidが渡される。
  • 計算量 $O(|str| + fによる寄与)$

• int size()...幾つの文字列が登録されているかを返す。

  • 計算量 $O(1)$
    • 備考
    • not verified

[Astral-23]

一旦nsで受け取る必要なくない? forの中に関数in

[Astral-23]

実際使う時は結構中身書き換える https://atcoder.jp/contests/agc047/submissions/58916625 insert/query/パラメータmakeの変更を抑えれば十分と思う この会では、queryにおいて、[0, i) + [i, n)にある任意の一文字　の分岐も許す $O(26 * n)$