前缀树

class TrieNode{
public:
    int pass;
    int end;
    vector<TrieNode*> nexts;
    TrieNode(){
        pass = 0;
        end = 0;
        for(int i = 0; i < 26; i++)
            nexts.push_back(nullptr);
    }
};
class Trie{
public:
    TrieNode *root;
    Trie(){
        root = new TrieNode();
    }
    void insert(string word){
        TrieNode *cur = root;
        cur -> pass++;
        for(int i = 0; i < word.size(); i++){
            int index = word[i] - 'a';
            if(cur -> nexts[index] == nullptr){
                cur -> nexts[index] = new TrieNode();
            }
            cur = cur -> nexts[index];
            cur -> pass++;
        }
        cur -> end++;
    }
    int search(string word){
        TrieNode *cur = root;
        for(int i = 0; i < word.size(); i++){
            int index = word[i] - 'a';
            if(cur -> nexts[index] == nullptr){
                return 0;
            }
            cur = cur -> nexts[index];
        }
        return cur -> end;
    }
    int prefix(string pre){
        TrieNode *cur = root;
        for(int i = 0; i < pre.size(); i++){
            int index = pre[i] - 'a';
            if(cur -> nexts[index] == nullptr){
                return 0;
            }
            cur = cur -> nexts[index];
        }
        return cur -> pass;
    }
    void mydelete(TrieNode *cur){
        TrieNode *next;
        while(cur){
            for(int i = 0; i < 26; i++){
                if(cur -> nexts[i] != nullptr){
                    next = cur -> nexts[i];
                }
            }
            delete(cur);
            cur = next;
            next = nullptr;
        }
    }
    void Triedelete(string word){
        if(search(word) != 0){
            TrieNode *cur = root;
            cur -> pass--;
            for(int i = 0; i < word.size(); i++){
                int index = word[i] - 'a';
                if(--(cur ->nexts[index] -> pass) == 0){
                    mydelete(cur -> nexts[index]);
                    cur -> nexts[index] = nullptr;
                    return;
                }
                cur = cur -> nexts[index];
            }
            cur -> end--;
        }
    }
};