字典树 + 01 Trie 树

class trie_string {
    static const int size = 1e5 + 10;  // 字符串总长度
    static const int e = 26;           // 字符集大小
    int idx;
    std::array<std::array<int, e>, size> tr;
    std::array<int, size> cnt;

    int newnode() {
        tr[idx].fill(0);
        cnt[idx] = 0;
        idx++;
        return idx - 1;
    }
    // 将字符转化为 0-base
    static int to_int(char c) {
        return c - 'a';
    }

public:
    trie_string() : idx(0) { newnode(); }
    void insert(const std::string &s) {
        int p = 0;
        for (auto i : s) {
            i = to_int(i);  // 要映射到0开始的喵
            if (!tr[p][i]) {
                tr[p][i] = newnode();
            }
            p = tr[p][i];
        }
        cnt[p]++;
    }
    void clean() {
        idx = 0;
        newnode();
    }
};

class trie_01 {
    static const int size = 1e5 * 30 + 10;  // 位数 * 数量
    static const int e = 2;                 // 01
    static const int n = 30;                // max = 2 ^ n - 1;
    int idx;
    std::array<std::array<int, e>, size> tr;
    std::array<int, size> cnt;

    int newnode() {
        tr[idx].fill(0);
        cnt[idx] = 0;
        idx++;
        return idx - 1;
    }

    static int to_int(int a, int d) {
        return (a >> d) & 1;
    }

public:
    trie_01() : idx(0) { newnode(); }
    void insert(int s) {
        int p = 0;
        for (int i = n - 1; i >= 0; i--) {
            int x = to_int(s, i);  // 要映射到0开始的喵
            if (!tr[p][x]) {
                tr[p][x] = newnode();
            }
            p = tr[p][x];
        }
        cnt[p]++;
    }
    void clean() {
        idx = 0;
        newnode();
    }
    // 查询子树和 mask xor 最小值
    int query_xor_min(int mask, int p = 0, int d = n - 1) {
        int res = 0;
        for (int i = d; i >= 0; i--) {
            int x = to_int(mask, i);
            if (tr[p][x])
                p = tr[p][x];
            else
                p = tr[p][!x], res += 1 << i;
        }
        return res;
    }
};