Trie
O(|s|) per operationPrefix tree over a fixed alphabet: insert and look up strings in time proportional to their length. The base structure for prefix counting, XOR-maximization (over bits), and DP over dictionaries.
// use it on
CSES: Word Combinations ↗
Count ways to build a string from dictionary words: DP over positions, where the trie enumerates every dictionary word starting at position i in O(length).
// the code
struct Trie { // lowercase a-z
vector<array<int, 26>> next;
vector<int> cnt; // words ending at this node
Trie() : next(1), cnt(1, 0) { next[0].fill(-1); }
void insert(const string& s) {
int v = 0;
for (char ch : s) {
int c = ch - 'a';
if (next[v][c] == -1) {
next[v][c] = next.size();
next.push_back({});
next.back().fill(-1);
cnt.push_back(0);
}
v = next[v][c];
}
cnt[v]++;
}
int count(const string& s) { // exact-match count
int v = 0;
for (char ch : s) {
v = next[v][ch - 'a'];
if (v == -1) return 0;
}
return cnt[v];
}
};