SyntaxPilot
Courses/Competitive Programming/Lesson 75
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Competitive Programming · Lesson 75 of 90

Trie and XOR-maximisation problems

queued

These are the notes for Competitive Programming episode 75. A trie (prefix tree) stores many strings so that every prefix is one node, shared by every word that starts with it. With a counter on every node, "how many words start with p?" costs only |p| steps. Contact Search shows the check-every-name brute force (TLE) and a real bug: counting only where a word ends gives 0 1 0 instead of 3 2 0. Signal Clash (the largest a_i XOR a_j) stores numbers as 20-bit words in a binary trie and walks greedily to the opposite bit from the highest bit down; walking from bit 0 up gives 15 instead of 30. Every C++ example was compiled with g++ -O2 -std=c++17 main.cpp -o main (g++ 13, the same command as the SyntaxPilot compiler); all outputs below are real.

The real-life hook

India Post does not compare every letter's full address with every area. It sorts by PIN code, one digit at a time: all letters starting with 1 go to one bin, then 11 to a smaller bin inside it, then 110. Every letter for an area shares that path, so the path exists once. If each bin keeps a counter of the letters that passed through it, then "how many letters are for areas starting with 110?" is just the counter on that bin. That tree of bins is a trie.

(Written for this course.)

  • n contact names (n ≤ 10^5, total length ≤ 10^6) and q prefixes (q ≤ 2·10^5, each at most 10 letters), all lowercase.
  • For each prefix, print how many names start with it.
4 3
chai chaiwala chana dosa
cha
chai
idli

cha → 3 (chai, chaiwala, chana), chai → 2, idli → 0.

Attempt 1: check every name (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<string> names(n);
    for (auto& w : names) cin >> w;
    while (q--) {
        string p;
        cin >> p;
        int c = 0;
        for (auto& w : names)                          // check every name
            if (w.compare(0, p.size(), p) == 0) c++;
        cout << c << "\n";
    }
}
4 3
chai chaiwala chana dosa
cha
chai
idli
3
2
0

Worst case: 100,000 names and 200,000 prefixes, all aaaaaaaaaa: 2·10^10 comparisons.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 100000, q = 200000;
    vector<string> names(n, string(10, 'a'));   // the worst case
    vector<string> qs(q, string(10, 'a'));
    ll total = 0;
    for (auto& p : qs)
        for (auto& w : names)                          // check every name
            if (w.compare(0, p.size(), p) == 0) total++;
    cout << total << "\n";
}
Time Limit Exceeded

In the SyntaxPilot compiler this shows Time Limit Exceeded.

The trie

  • The root is the empty prefix; each edge adds one letter, so each node is one prefix.
  • nxt[v][c] = the child of node v for letter c, 0 = no child yet (node 0 is the root, which is never anyone's child).
  • insert(w): walk from the root, create missing nodes, and do cnt[v]++ on every node passed.
  • count(p): walk p's letters; a missing child means no name has this prefix (0); otherwise answer cnt at the last node.
root (4)
 ├─ c (3) ─ h (3) ─ a (3) ─┬─ i (2) ─ w ─ a ─ l ─ a (1)
 │                         └─ n (1) ─ a (1)
 └─ d (1) ─ o ─ s ─ a (1)

Each insert and query costs the length of its string.

Counting at the wrong place

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Trie {
    vector<array<int, 26>> nxt;                     // nxt[v][c]: the child for letter c
    vector<int> cnt;                                // names passing through each node
    Trie() { nxt.push_back({}); cnt.push_back(0); } // node 0 is the root
    void insert(const string& w) {
        int v = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({}); cnt.push_back(0); }
            v = nxt[v][c];
        }
        cnt[v]++;                                   // one more name ends here
    }
    int count(const string& p) {
        int v = 0;
        for (char ch : p) {
            v = nxt[v][ch - 'a'];
            if (!v) return 0;                       // no name has this prefix
        }
        return cnt[v];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<string> names(n);
    for (auto& w : names) cin >> w;
    Trie t;
    for (auto& w : names) t.insert(w);
    while (q--) {
        string p;
        cin >> p;
        cout << t.count(p) << "\n";
    }
}
4 3
chai chaiwala chana dosa
cha
chai
idli
0
1
0

No name ends exactly at cha, so its counter is 0. That counts names equal to the prefix, not names that start with it.

The fix: count on the way down

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Trie {
    vector<array<int, 26>> nxt;                     // nxt[v][c]: the child for letter c
    vector<int> cnt;                                // names passing through each node
    Trie() { nxt.push_back({}); cnt.push_back(0); } // node 0 is the root
    void insert(const string& w) {
        int v = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({}); cnt.push_back(0); }
            v = nxt[v][c];
            cnt[v]++;                               // one more name passes here
        }
    }
    int count(const string& p) {
        int v = 0;
        for (char ch : p) {
            v = nxt[v][ch - 'a'];
            if (!v) return 0;                       // no name has this prefix
        }
        return cnt[v];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<string> names(n);
    for (auto& w : names) cin >> w;
    Trie t;
    for (auto& w : names) t.insert(w);
    while (q--) {
        string p;
        cin >> p;
        cout << t.count(p) << "\n";
    }
}
4 3
chai chaiwala chana dosa
cha
chai
idli
3
2
0

A prefix longer than every name, and a prefix that is a whole name:

2 2
ab abc
abcd
ab
0
2

The worst case:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Trie {
    vector<array<int, 26>> nxt;                     // nxt[v][c]: the child for letter c
    vector<int> cnt;                                // names passing through each node
    Trie() { nxt.push_back({}); cnt.push_back(0); } // node 0 is the root
    void insert(const string& w) {
        int v = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({}); cnt.push_back(0); }
            v = nxt[v][c];
            cnt[v]++;                               // one more name passes here
        }
    }
    int count(const string& p) {
        int v = 0;
        for (char ch : p) {
            v = nxt[v][ch - 'a'];
            if (!v) return 0;                       // no name has this prefix
        }
        return cnt[v];
    }
};

int main() {
    int n = 100000, q = 200000;
    vector<string> names(n, string(10, 'a'));   // the worst case
    vector<string> qs(q, string(10, 'a'));
    ll total = 0;
    Trie t;
    for (auto& w : names) t.insert(w);
    for (auto& p : qs) total += t.count(p);
    cout << total << "\n";
}
20000000000

Stress test

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Trie {
    vector<array<int, 26>> nxt;                     // nxt[v][c]: the child for letter c
    vector<int> cnt;                                // names passing through each node
    Trie() { nxt.push_back({}); cnt.push_back(0); } // node 0 is the root
    void insert(const string& w) {
        int v = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({}); cnt.push_back(0); }
            v = nxt[v][c];
            cnt[v]++;                               // one more name passes here
        }
    }
    int count(const string& p) {
        int v = 0;
        for (char ch : p) {
            v = nxt[v][ch - 'a'];
            if (!v) return 0;                       // no name has this prefix
        }
        return cnt[v];
    }
};

int main() {
    mt19937 gen(75);
    for (int t = 1; t <= 500; t++) {
        int n = gen() % 8 + 1;
        vector<string> names(n);
        Trie tr;
        for (auto& w : names) {
            w = string(gen() % 5 + 1, 'a');
            for (char& c : w) c = 'a' + gen() % 2;
            tr.insert(w);
        }
        string p(gen() % 4 + 1, 'a');
        for (char& c : p) c = 'a' + gen() % 2;
        int slow = 0;
        for (auto& w : names) if (w.compare(0, p.size(), p) == 0) slow++;
        if (slow != tr.count(p)) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Problem T2 · Signal Clash

(Written for this course.)

  • n radio signals (2 ≤ n ≤ 2·10^6), each an integer 0 ≤ a_i < 2^20.
  • Two signals clash with strength a_i XOR a_j. Print the strongest clash.
5
18 7 25 12 3

25 = 11001, 7 = 00111, 25 XOR 7 = 11110 = 30. (XOR gives 1 exactly in the bits where the two numbers differ.)

Attempt 1: every pair (TLE)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    int best = 0;
    for (int i = 0; i < n; i++)                    // every pair
        for (int j = i + 1; j < n; j++) best = max(best, a[i] ^ a[j]);
    cout << best << "\n";
}
5
18 7 25 12 3
30
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    int n = 2000000;
    mt19937 gen(1);
    vector<int> a(n);
    for (int& x : a) x = gen() % (1 << 20);         // the worst case
    int best = 0;
    for (int i = 0; i < n; i++)                    // every pair
        for (int j = i + 1; j < n; j++) best = max(best, a[i] ^ a[j]);
    cout << best << "\n";
}
Time Limit Exceeded

n²/2 = 2·10^12 XORs: Time Limit Exceeded.

The binary trie and the greedy walk

  • Write every number as 20 bits, highest first, and insert it into a trie whose nodes have two children (bit 0, bit 1).
  • For each x, walk from bit 19 down: if a child with the opposite bit exists, go there and set that bit of the answer; otherwise take the same bit (that bit of the XOR is 0).
  • Why greedy is safe: 2^b > 2^(b−1) + … + 2^0, so 10000 beats 01111. Winning the highest possible bit is always worth more than everything below it.
  • 20 steps per insert and per query: O(20 · n).

The bottom-up bug

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BitTrie {
    vector<array<int, 2>> nxt;
    BitTrie() { nxt.push_back({0, 0}); }
    void insert(int x) {
        int v = 0;
        for (int b = 0; b <= 19; b++) {
            int c = x >> b & 1;
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({0, 0}); }
            v = nxt[v][c];
        }
    }
    int best(int x) {                               // the largest x ^ y over inserted y
        int v = 0, res = 0;
        for (int b = 0; b <= 19; b++) {
            int c = x >> b & 1;
            if (nxt[v][!c]) res |= 1 << b, v = nxt[v][!c];   // the opposite bit wins
            else v = nxt[v][c];
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    BitTrie t;
    for (int x : a) t.insert(x);
    int ans = 0;
    for (int x : a) ans = max(ans, t.best(x));
    cout << ans << "\n";
}
5
18 7 25 12 3
15

Walking from bit 0 wins the small bits first and gives up the big ones; low bits can never make up for a lost high bit.

The fix: from the highest bit down

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BitTrie {
    vector<array<int, 2>> nxt;
    BitTrie() { nxt.push_back({0, 0}); }
    void insert(int x) {
        int v = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({0, 0}); }
            v = nxt[v][c];
        }
    }
    int best(int x) {                               // the largest x ^ y over inserted y
        int v = 0, res = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (nxt[v][!c]) res |= 1 << b, v = nxt[v][!c];   // the opposite bit wins
            else v = nxt[v][c];
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    BitTrie t;
    for (int x : a) t.insert(x);
    int ans = 0;
    for (int x : a) ans = max(ans, t.best(x));
    cout << ans << "\n";
}
5
18 7 25 12 3
30

Equal signals:

3
6 6 6
0

0 and the largest possible value:

2
0 1048575
1048575

Two million random signals:

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BitTrie {
    vector<array<int, 2>> nxt;
    BitTrie() { nxt.push_back({0, 0}); }
    void insert(int x) {
        int v = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({0, 0}); }
            v = nxt[v][c];
        }
    }
    int best(int x) {                               // the largest x ^ y over inserted y
        int v = 0, res = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (nxt[v][!c]) res |= 1 << b, v = nxt[v][!c];   // the opposite bit wins
            else v = nxt[v][c];
        }
        return res;
    }
};

int main() {
    int n = 2000000;
    mt19937 gen(1);
    vector<int> a(n);
    for (int& x : a) x = gen() % (1 << 20);         // the worst case
    BitTrie t;
    for (int x : a) t.insert(x);
    int ans = 0;
    for (int x : a) ans = max(ans, t.best(x));
    cout << ans << "\n";
}
1048575

Stress test

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BitTrie {
    vector<array<int, 2>> nxt;
    BitTrie() { nxt.push_back({0, 0}); }
    void insert(int x) {
        int v = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({0, 0}); }
            v = nxt[v][c];
        }
    }
    int best(int x) {                               // the largest x ^ y over inserted y
        int v = 0, res = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (nxt[v][!c]) res |= 1 << b, v = nxt[v][!c];   // the opposite bit wins
            else v = nxt[v][c];
        }
        return res;
    }
};

int main() {
    mt19937 gen(75);
    for (int t = 1; t <= 500; t++) {
        int n = gen() % 10 + 2;
        vector<int> a(n);
        BitTrie tr;
        for (int& x : a) x = gen() % 64, tr.insert(x);
        int slow = 0, fast = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++) slow = max(slow, a[i] ^ a[j]);
        for (int x : a) fast = max(fast, tr.best(x));
        if (slow != fast) { cout << "mismatch on test " << t; return 0; }
    }
    cout << "all 500 tests passed";
}
all 500 tests passed

Complexity vs the constraints

Method Time Verdict
T1: check every name O(n · q · len) ≈ 2·10^10 TLE
T1: trie O(total length of names + prefixes) accepted
T2: every pair O(n²) ≈ 2·10^12 TLE
T2: binary trie O(20 · n) = 4·10^7 accepted (~0.5 s)

Memory. A trie has at most (total length + 1) nodes. With 26 int children per node, a million letters is about 100 MB, so always size it from the constraints (or use map/sorted children when the alphabet is big). For the bit trie, 2·10^6 numbers × 20 bits looks like 4·10^7 nodes, but 20-bit values have at most 2^21 different prefixes, so it stays near 2 million nodes.

Common mistakes (and the real outputs)

Mistake What you see Why Fix
cnt[v]++ only where a word ends 0 1 0 instead of 3 2 0 counts equal words, not prefixes cnt[v]++ on every node passed
walking bits from bit 0 up 15 instead of 30 a high bit beats all lower bits for (int b = 19; b >= 0; b--)
not checking for a missing child walks back to the root, wrong count 0 means "no child" if (!v) return 0;
too many nodes Memory Limit Exceeded 26 ints per node size from the constraints
too few bits Wrong Answer for big values high bits never inserted bits = ⌈log2(max value)⌉
nxt[v][c] = nxt.size() after push_back off by one, broken links the new index is the old size take the index before push_back

Mini project

Build a tiny autocomplete: insert a list of words with how often each was searched, and for every typed prefix print the most searched word that starts with it (store the best word index on every node during insert).

Practice

These are the homework problems from the episode.

1. How many names are prefixes of a given word? Store at each node how many names end there (here that is exactly what you want), and add them up while walking the word.

2. The largest XOR of any subarray. With prefix XORs pre_i = a_0 ^ … ^ a_i, the XOR of a[j..i] is pre_i ^ pre_(j−1). Insert 0 first, then for each i query the trie with pre_i before inserting it.

Solutions for 1 and 2 (checked against brute force on 100 random tests)
#include <bits/stdc++.h>
using namespace std;

int main() {                                        // how many names are prefixes of a word?
    int n;
    cin >> n;
    vector<array<int, 26>> nxt(1);
    vector<int> ends(1, 0);                         // names that END at each node
    for (int i = 0; i < n; i++) {
        string w;
        cin >> w;
        int v = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({}); ends.push_back(0); }
            v = nxt[v][c];
        }
        ends[v]++;
    }
    string word;
    cin >> word;
    int v = 0, total = 0;
    for (char ch : word) {
        v = nxt[v][ch - 'a'];
        if (!v) break;
        total += ends[v];                           // a name ends here: it is a prefix of word
    }
    cout << total << "\n";
}
3
ch cha dosa
chai
2
#include <bits/stdc++.h>
using namespace std;

int main() {                                        // the largest XOR of any subarray
    int n;
    cin >> n;
    vector<array<int, 2>> nxt(1, {0, 0});
    auto insert = [&](int x) {
        int v = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({0, 0}); }
            v = nxt[v][c];
        }
    };
    auto best = [&](int x) {
        int v = 0, res = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (nxt[v][!c]) res |= 1 << b, v = nxt[v][!c];
            else v = nxt[v][c];
        }
        return res;
    };
    int pre = 0, ans = 0;
    insert(0);                                      // the empty prefix
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        pre ^= x;                                   // xor of a[0..i]
        ans = max(ans, best(pre));                  // xor of a[j..i] = pre_i ^ pre_(j-1)
        insert(pre);
    }
    cout << ans << "\n";
}
4
1 2 3 4
7

3. The largest XOR with x using only numbers ≤ m. Offline: sort the queries by m and the numbers by value, insert numbers as m grows, then query.

Hint

Two pointers over the sorted numbers and the sorted queries; each number is inserted once, each query costs 20 steps: O((n + q) log + 20 (n + q)).

4. Delete a name from the trie. Walk the name and do cnt[v]-- on every node passed (the nodes can stay; a count of 0 means no live name uses that prefix).

Hint

For the XOR trie, keep a counter per node too and treat a child with counter 0 as missing in best.

Quick quiz

// the trie holds 2 (010), 5 (101), 7 (111)
// query x = 3 (011), walking from the top bit
// which y, and what is 3 ^ y?

A) y = 5, XOR 6 · B) y = 7, XOR 4 · C) y = 2, XOR 1 · D) y = 7, XOR 6

Answer

A. The top bit of 3 is 0 → go to 1 (5 or 7). The next bit is 1 → go to 0: only 5 (101). The last bit is forced. 3 ^ 5 = 110 = 6.

Interview questions

  1. What is a trie? A tree where each node is a prefix and each edge adds one character; words sharing a prefix share its path.
  2. How do you count words with a given prefix? Keep a counter on every node, incremented on every node an insert passes; answer the counter at the prefix's node.
  3. Complexity of trie operations? O(length of the string) per insert or query, independent of the number of words.
  4. How do you find the maximum XOR pair? Insert all numbers bit by bit (highest first) into a binary trie; for each number walk to the opposite bit whenever possible.
  5. Why must the walk start from the highest bit? A 1 in bit b is worth more than all lower bits combined.
  6. Trie vs hash set of prefixes? A hash set needs every prefix of every word stored separately (O(Σ len²) memory); the trie stores each prefix once.
  7. How do you reduce trie memory? Smaller alphabets, map/sorted children, or a compressed (radix) trie.

Glossary

Term Meaning Example
Trie (prefix tree) A tree with one node per prefix the PIN-code bins
Root The node for the empty prefix node 0
Node One prefix cha
Edge One more letter cha → chai
nxt[v][c] The child of v for letter c; 0 = none nxt[root]['c']
cnt[v] Words passing through node v 3 at cha
Prefix query How many words start with p cha → 3
XOR (^) 1 in every bit where two numbers differ 25 ^ 7 = 30
Binary trie A trie over the bits of numbers, two children per node 20 levels
Greedy Take the best choice at each step the opposite bit
Most significant bit The highest bit, worth the most bit 19
Prefix XOR a_0 ^ … ^ a_i subarray XORs
Memory Limit Exceeded (MLE) The program used more memory than allowed 26 ints × too many nodes
Stress test Fast vs brute force on many random inputs all 500 tests passed
Aho-Corasick A trie with fall back links (next episode) many patterns at once

Summary

  • A trie stores every prefix once; cnt[v]++ on every node passed makes a prefix query O(|p|).
  • Numbers become 20-bit words in a binary trie; walking to the opposite bit from the top gives the maximum XOR in O(20 · n).
  • Size the trie from the constraints: memory is usually the limit, not time.

Solutions in C++, Java and Python

Problem T1 · Contact Search

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct Trie {
    vector<array<int, 26>> nxt;                     // nxt[v][c]: the child for letter c
    vector<int> cnt;                                // names passing through each node
    Trie() { nxt.push_back({}); cnt.push_back(0); } // node 0 is the root
    void insert(const string& w) {
        int v = 0;
        for (char ch : w) {
            int c = ch - 'a';
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({}); cnt.push_back(0); }
            v = nxt[v][c];
            cnt[v]++;                               // one more name passes here
        }
    }
    int count(const string& p) {
        int v = 0;
        for (char ch : p) {
            v = nxt[v][ch - 'a'];
            if (!v) return 0;                       // no name has this prefix
        }
        return cnt[v];
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, q;
    cin >> n >> q;
    vector<string> names(n);
    for (auto& w : names) cin >> w;
    Trie t;
    for (auto& w : names) t.insert(w);
    while (q--) {
        string p;
        cin >> p;
        cout << t.count(p) << "\n";
    }
}

Java (checked on the samples)

import java.io.*;
import java.util.*;

public class Main {
    static int[][] nxt = new int[1_000_001][26];       // nxt[v][c]: the child for letter c (0 = none)
    static int[] cnt = new int[1_000_001];             // names passing through each node
    static int nodes = 1;                              // node 0 is the root

    static void insert(String w) {
        int v = 0;
        for (int i = 0; i < w.length(); i++) {
            int c = w.charAt(i) - 'a';
            if (nxt[v][c] == 0) nxt[v][c] = nodes++;
            v = nxt[v][c];
            cnt[v]++;                                  // one more name passes here
        }
    }

    static int count(String p) {
        int v = 0;
        for (int i = 0; i < p.length(); i++) {
            v = nxt[v][p.charAt(i) - 'a'];
            if (v == 0) return 0;                      // no name has this prefix
        }
        return cnt[v];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        in.nextToken(); int n = (int) in.nval;
        in.nextToken(); int q = (int) in.nval;
        for (int i = 0; i < n; i++) { in.nextToken(); insert(in.sval); }
        StringBuilder out = new StringBuilder();
        for (int i = 0; i < q; i++) { in.nextToken(); out.append(count(in.sval)).append('\n'); }
        System.out.print(out);
    }
}

Python

import sys

def main():
    data = sys.stdin.read().split()
    n, q = int(data[0]), int(data[1])
    nxt = [{}]                       # nxt[v][letter]: the child (a dict per node)
    cnt = [0]                        # names passing through each node
    for w in data[2:2 + n]:
        v = 0
        for ch in w:
            if ch not in nxt[v]:
                nxt[v][ch] = len(nxt)
                nxt.append({})
                cnt.append(0)
            v = nxt[v][ch]
            cnt[v] += 1              # one more name passes here
    out = []
    for p in data[2 + n:2 + n + q]:
        v = 0
        for ch in p:
            v = nxt[v].get(ch, -1)
            if v < 0:
                break                # no name has this prefix
        out.append(cnt[v] if v >= 0 else 0)
    print("\n".join(map(str, out)))

main()

Problem T2 · Signal Clash

C++

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

struct BitTrie {
    vector<array<int, 2>> nxt;
    BitTrie() { nxt.push_back({0, 0}); }
    void insert(int x) {
        int v = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (!nxt[v][c]) { nxt[v][c] = nxt.size(); nxt.push_back({0, 0}); }
            v = nxt[v][c];
        }
    }
    int best(int x) {                               // the largest x ^ y over inserted y
        int v = 0, res = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (nxt[v][!c]) res |= 1 << b, v = nxt[v][!c];   // the opposite bit wins
            else v = nxt[v][c];
        }
        return res;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    vector<int> a(n);
    for (int& x : a) cin >> x;
    BitTrie t;
    for (int x : a) t.insert(x);
    int ans = 0;
    for (int x : a) ans = max(ans, t.best(x));
    cout << ans << "\n";
}

Java (checked on the samples)

import java.io.*;

public class Main {
    static int[][] nxt = new int[2 * (1 << 20) + 1][2];   // at most 2^21 different prefixes of 20 bits
    static int nodes = 1;

    static void insert(int x) {
        int v = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (nxt[v][c] == 0) nxt[v][c] = nodes++;
            v = nxt[v][c];
        }
    }

    static int best(int x) {                           // the largest x ^ y over inserted y
        int v = 0, res = 0;
        for (int b = 19; b >= 0; b--) {
            int c = x >> b & 1;
            if (nxt[v][c ^ 1] != 0) { res |= 1 << b; v = nxt[v][c ^ 1]; }   // the opposite bit wins
            else v = nxt[v][c];
        }
        return res;
    }

    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken(); int n = (int) in.nval;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) { in.nextToken(); a[i] = (int) in.nval; insert(a[i]); }
        int ans = 0;
        for (int x : a) ans = Math.max(ans, best(x));
        System.out.println(ans);
    }
}

Python

import sys

def main():
    data = sys.stdin.buffer.read().split()
    n = int(data[0])
    a = list(map(int, data[1:1 + n]))
    zero, one = [0], [0]             # children of each node (0 = none)
    for x in a:
        v = 0
        for b in range(19, -1, -1):
            kids = one if x >> b & 1 else zero
            if not kids[v]:
                kids[v] = len(zero)
                zero.append(0)
                one.append(0)
            v = kids[v]
    ans = 0
    for x in a:
        v = res = 0
        for b in range(19, -1, -1):
            if x >> b & 1:
                want, other = zero, one
            else:
                want, other = one, zero
            if want[v]:
                res |= 1 << b        # the opposite bit wins
                v = want[v]
            else:
                v = other[v]
        ans = max(ans, res)
    print(ans)

main()