Trie Tree

 avatar
unknown
c_cpp
3 years ago
1.1 kB
6
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);
    }

};