Trie (Prefix Tree)

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Trie for lowercase English letters 'a'..'z'.
5
// Stores pass and end counts to support duplicate words and erasure.
6
struct Trie {
7
    struct Node {
8
        int next[26];   // child indices; -1 means absent
9
        int pass = 0;   // how many words pass through this node
10
        int end = 0;    // how many words end at this node
11
        Node() { fill(begin(next), end(next), -1); }
12
    };
13
14
    vector<Node> t; // node pool; node 0 is the root
15
16
    Trie() { t.emplace_back(); }
17
18
    // Helper: map char to index [0..25]; assumes input is 'a'..'z'
19
    static inline int idx(char c) { return c - 'a'; }
20
21
    void insert(const string &s) {
22
        int v = 0;
23
        t[v].pass++; // root pass can record how many total words inserted
24
        for (char ch : s) {
25
            int c = idx(ch);
26
            if (c < 0 || c >= 26) throw runtime_error("Non-lowercase character");
27
            if (t[v].next[c] == -1) {
28
                t[v].next[c] = (int)t.size();
29
                t.emplace_back();
30
            }
31
            v = t[v].next[c];
32
            t[v].pass++;
33
        }
34
        t[v].end++;
35
    }
36
37
    int countWordsEqualTo(const string &s) const {
38
        int v = 0;
39
        for (char ch : s) {
40
            int c = idx(ch);
41
            if (c < 0 || c >= 26) return 0;
42
            int u = t[v].next[c];
43
            if (u == -1) return 0;
44
            v = u;
45
        }
46
        return t[v].end;
47
    }
48
49
    int countWordsStartingWith(const string &pref) const {
50
        int v = 0;
51
        for (char ch : pref) {
52
            int c = idx(ch);
53
            if (c < 0 || c >= 26) return 0;
54
            int u = t[v].next[c];
55
            if (u == -1) return 0;
56
            v = u;
57
        }
58
        return t[v].pass;
59
    }
60
61
    bool erase(const string &s) {
62
        if (countWordsEqualTo(s) == 0) return false; // word not present
63
        int v = 0;
64
        t[v].pass--;
65
        for (char ch : s) {
66
            int c = idx(ch);
67
            int u = t[v].next[c];
68
            v = u;
69
            t[v].pass--;
70
        }
71
        t[v].end--;
72
        // Note: We don't physically remove nodes to keep code simple.
73
        return true;
74
    }
75
};
76
77
int main() {
78
    ios::sync_with_stdio(false);
79
    cin.tie(nullptr);
80
81
    Trie tr;
82
    vector<string> words = {"app", "apple", "apply", "app", "apt"};
83
    for (auto &w : words) tr.insert(w);
84
85
    cout << tr.countWordsEqualTo("app") << "\n";       // 2
86
    cout << tr.countWordsStartingWith("ap") << "\n";    // 5
87
    cout << tr.countWordsStartingWith("app") << "\n";   // 4
88
89
    tr.erase("app");
90
    cout << tr.countWordsEqualTo("app") << "\n";       // 1
91
92
    cout << (tr.countWordsEqualTo("apple") ? "YES" : "NO") << "\n"; // YES
93
    cout << (tr.countWordsEqualTo("banana") ? "YES" : "NO") << "\n"; // NO
94
    return 0;
95
}
96

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct Trie {
5
    struct Node {
6
        int next[26];
7
        int pass = 0;
8
        int end = 0;
9
        Node() { fill(begin(next), end(next), -1); }
10
    };
11
    vector<Node> t;
12
    Trie() { t.emplace_back(); }
13
    static inline int idx(char c) { return c - 'a'; }
14
15
    void insert(string s) {
16
        for (char &c : s) c = char(tolower(c));
17
        int v = 0; t[v].pass++;
18
        for (char ch : s) {
19
            if (ch < 'a' || ch > 'z') continue; // skip non-letters to be robust
20
            int c = idx(ch);
21
            if (t[v].next[c] == -1) { t[v].next[c] = (int)t.size(); t.emplace_back(); }
22
            v = t[v].next[c];
23
            t[v].pass++;
24
        }
25
        t[v].end++;
26
    }
27
28
    // Find the node of a prefix; return -1 if absent.
29
    int findNode(const string &pref) const {
30
        int v = 0;
31
        for (char ch : pref) {
32
            if (ch < 'a' || ch > 'z') continue;
33
            int c = idx(ch);
34
            int u = t[v].next[c];
35
            if (u == -1) return -1;
36
            v = u;
37
        }
38
        return v;
39
    }
40
41
    void dfsCollect(int v, string &path, vector<string> &out, size_t K) const {
42
        if (out.size() >= K) return;
43
        if (t[v].end > 0) {
44
            // If the same word was inserted multiple times, we can push duplicates or one; here push once.
45
            out.push_back(path);
46
            if (out.size() >= K) return;
47
        }
48
        for (int c = 0; c < 26; ++c) {
49
            int u = t[v].next[c];
50
            if (u == -1) continue;
51
            path.push_back(char('a' + c));
52
            dfsCollect(u, path, out, K);
53
            path.pop_back();
54
            if (out.size() >= K) return; // early stop
55
        }
56
    }
57
58
    vector<string> autocomplete(string prefix, size_t K) const {
59
        for (char &c : prefix) c = char(tolower(c));
60
        vector<string> res;
61
        int v = findNode(prefix);
62
        if (v == -1) return res;
63
        string path = "";
64
        // Reconstruct the path from prefix's normalized letters only
65
        for (char ch : prefix) if ('a' <= ch && ch <= 'z') path.push_back(ch);
66
        dfsCollect(v, path, res, K);
67
        return res;
68
    }
69
};
70
71
int main() {
72
    ios::sync_with_stdio(false);
73
    cin.tie(nullptr);
74
75
    Trie tr;
76
    vector<string> dict = {"Alice", "Ali", "Alina", "Aliter", "Bob", "Bobby", "Alloy"};
77
    for (auto &w : dict) tr.insert(w);
78
79
    auto ans = tr.autocomplete("ali", 3);
80
    for (auto &s : ans) cout << s << "\n"; // ali, alice, alina (lexicographic among normalized)
81
82
    return 0;
83
}
84

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct BinaryTrie {
5
    struct Node {
6
        int nxt[2];
7
        int cnt; // how many numbers pass through this node
8
        Node() { nxt[0] = nxt[1] = -1; cnt = 0; }
9
    };
10
    vector<Node> t;
11
    static constexpr int W = 31; // use bits 31..0 (32-bit)
12
    BinaryTrie() { t.emplace_back(); }
13
14
    void insert(uint32_t x) {
15
        int v = 0; t[v].cnt++;
16
        for (int b = W; b >= 0; --b) {
17
            int bit = (x >> b) & 1u;
18
            if (t[v].nxt[bit] == -1) { t[v].nxt[bit] = (int)t.size(); t.emplace_back(); }
19
            v = t[v].nxt[bit];
20
            t[v].cnt++;
21
        }
22
    }
23
24
    // Optional: erase if multiset behavior needed
25
    bool erase(uint32_t x) {
26
        int v = 0; if (t[v].cnt == 0) return false; t[v].cnt--;
27
        for (int b = W; b >= 0; --b) {
28
            int bit = (x >> b) & 1u;
29
            int u = t[v].nxt[bit]; if (u == -1) return false;
30
            v = u; t[v].cnt--;
31
        }
32
        return true;
33
    }
34
35
    // Maximize x XOR y over all inserted y.
36
    uint32_t maxXorWith(uint32_t x) const {
37
        int v = 0;
38
        if (t[v].cnt == 0) return 0; // empty trie
39
        uint32_t ans = 0;
40
        for (int b = W; b >= 0; --b) {
41
            int bit = (x >> b) & 1u;
42
            int want = bit ^ 1; // prefer opposite bit
43
            int go = (t[v].nxt[want] != -1 && t[t[v].nxt[want]].cnt > 0) ? want : bit;
44
            v = t[v].nxt[go];
45
            ans |= uint32_t((go ^ bit)) << b; // set bit if we took opposite
46
        }
47
        return ans; // value of (x XOR best_y)
48
    }
49
};
50
51
uint32_t maxXorPair(const vector<uint32_t>& a) {
52
    BinaryTrie bt;
53
    uint32_t best = 0;
54
    for (uint32_t x : a) {
55
        if (!bt.t.empty() && bt.t[0].cnt > 0) best = max(best, bt.maxXorWith(x));
56
        bt.insert(x);
57
    }
58
    return best;
59
}
60
61
int main() {
62
    ios::sync_with_stdio(false);
63
    cin.tie(nullptr);
64
65
    vector<uint32_t> arr = {3, 10, 5, 25, 2, 8};
66
    cout << maxXorPair(arr) << "\n"; // 28 (5 ^ 25)
67
68
    BinaryTrie bt;
69
    for (auto x : arr) bt.insert(x);
70
    cout << bt.maxXorWith(10) << "\n"; // best XOR value with 10 is 19 (10 ^ 25)
71
72
    return 0;
73
}
74

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
struct MapTrie {
5
    struct Node {
6
        unordered_map<char,int> next; // only store existing edges
7
        int pass = 0, end = 0;
8
    };
9
    vector<Node> t;
10
    MapTrie() { t.emplace_back(); }
11
12
    void insert(const string &s) {
13
        int v = 0; t[v].pass++;
14
        for (char ch : s) {
15
            auto it = t[v].next.find(ch);
16
            if (it == t[v].next.end()) {
17
                t[v].next[ch] = (int)t.size();
18
                t.emplace_back();
19
            }
20
            v = t[v].next[ch];
21
            t[v].pass++;
22
        }
23
        t[v].end++;
24
    }
25
26
    int countPrefix(const string &p) const {
27
        int v = 0;
28
        for (char ch : p) {
29
            auto it = t[v].next.find(ch);
30
            if (it == t[v].next.end()) return 0;
31
            v = it->second;
32
        }
33
        return t[v].pass;
34
    }
35
36
    bool contains(const string &s) const {
37
        int v = 0;
38
        for (char ch : s) {
39
            auto it = t[v].next.find(ch);
40
            if (it == t[v].next.end()) return false;
41
            v = it->second;
42
        }
43
        return t[v].end > 0;
44
    }
45
};
46
47
int main() {
48
    ios::sync_with_stdio(false);
49
    cin.tie(nullptr);
50
51
    MapTrie tr;
52
    // Works with mixed characters without normalization
53
    vector<string> keys = {"key-1", "key:2", "kéy", "Key"};
54
    for (auto &s : keys) tr.insert(s);
55
56
    cout << tr.contains("key-1") << "\n";   // 1
57
    cout << tr.countPrefix("key") << "\n";  // >= 2 depending on entries
58
    cout << tr.contains("KEY") << "\n";     // 0 (case-sensitive)
59
    return 0;
60
}
61