Trie Tree
unknown
c_cpp
3 years ago
1.1 kB
7
Indexable
struct TrieTree { int n, root; int MAX, ALPHABET; vector<vector<int> > next; vector<int> data; void init(int MAX, int ALPHABET) { root = 0, n = 1; data[root] = 0; next.resize(MAX); for(int i = 0; i < MAX; ++i){ next[i].resize(ALPHABET); for(int j = 0; j < ALPHABET; ++j) next[i][j] = -1; } data.resize(MAX); } void insert(char *s) { int curr = root, i, k; for(i = 0; s[i]; i++) { k = s[i]-'a'; if(next[curr][k] == -1) { next[curr][k] = n; data[n] = s[i]; // optional for(int j = 0; j < ALPHABET;++j) next[n][j]=-1; n++; } curr = next[curr][k]; } data[curr] = 0; // sentinel, optional } bool find(char *s) { int curr = root, i, k; for(i = 0; s[i]; i++) { k = s[i]-'a'; if(next[curr][k] == -1) return false; curr = next[curr][k]; } return (data[curr] == 0); } };
Editor is loading...