datastructures/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

//nur für kleinbuchstaben!
struct node {
	node *(e)[26];
	int c = 0;//anzahl der wörter die an dem node enden.
	node() { for(int i = 0; i < 26; i++) e[i] = NULL; }	
};

void insert(node *root, string *txt, int s) {
	if(s >= txt->length()) root->c++;
	else {
		int idx = (int)((*txt).at(s) - 'a');
		if(root->e[idx] == NULL) {
			root->e[idx] = new node();
		}
		insert(root->e[idx], txt, s+1);
	}
}

int contains(node *root, string *txt, int s) {
	if(s >= txt->length()) return root->c;
	int idx = (int)((*txt).at(s) - 'a');
	if(root->e[idx] != NULL) {
			return contains(root->e[idx], txt, s+1);
	} else return 0;
}