content/string/trie.cpp


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

// Zahlenwerte müssen bei 0 beginnen und zusammenhängend sein.
constexpr int ALPHABET_SIZE = 2;
struct node {
	int words, ends;
	array<int, ALPHABET_SIZE> nxt;
	node() : words(0), ends(0) {fill(all(nxt), -1);}
};
vector<node> trie = {node()};

int traverse(const vector<int>& word, int x) {
	int id = 0;
	for (int c : word) {
		if (trie[id].words == 0 && x <= 0) return -1;
		trie[id].words += x;
		if (trie[id].nxt[c] < 0 && x > 0) {
			trie[id].nxt[c] = sz(trie);
			trie.emplace_back();
		}
		id = trie[id].nxt[c];
		if (id < 0) return -1;
	}
	trie[id].words += x;
	trie[id].ends += x;
	return id;
}

int insert(const vector<int>& word) {
	return traverse(word, 1);
}
bool erase(const vector<int>& word) {
	int id = traverse(word, 0);
	if (id < 0 || trie[id].ends <= 0) return false;
	traverse(word, -1);
	return true;
}