#include <iostream>
#include <vector>
#include <string>
using namespace std;
//26 個小寫英文字母
#define NUM 26
class Trie{
private:
    Trie* arr[NUM];//多叉樹(最大26個分支，因?yàn)?6個小寫字母嘛)
    int end;  //代表word完整單詞的個數(shù)，0就是無此單詞，只是一個前綴;insert一個單詞的時候，這個單詞的end首次出現(xiàn)就置為1;之后重復(fù)插入就end++;
    int pass; //代表以此前綴為公共前綴的節(jié)點(diǎn)個數(shù),每次insert的時候會調(diào)整;
public:
    Trie() {
        memset(arr,0,sizeof(arr));//每個新節(jié)點(diǎn)的映射數(shù)組內(nèi)容置nullptr
	    end = 0;
        ncount = 0; //初始化時以該映射信息字符為前綴的個數(shù)為1(這個字符本身算的1)
    }
    //插入單詞
    void Insert(string &x)
    {
    }
    //查找 完全匹配字符串x 的數(shù)量
    int Find(string &x)
    {
    }
    //查找 前綴為字符串x 的數(shù)量
    int FindContain(string& x)
    {
    }
    //刪除某個單詞(前綴)
    bool Erase(string &x)
    {
    }
    ~Trie()
    {
        //因?yàn)閚ew了26個連續(xù)的tire*空間，不要某個節(jié)點(diǎn)，不要把它對應(yīng)給下層準(zhǔn)備的26個空間也delete掉 防止內(nèi)存泄漏
        for (int i = 0; i < NUMBER; i++)
		{
			if (nexts[i]){
                delete nexts[i];
            }
		}
    }
};

//插入單詞
    void Insert(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        cur->pass++;//不管insert啥，我們root空節(jié)點(diǎn)的pass相當(dāng)于必須+1，最終這個root->pass可以代表一共insert了幾次=-=
        for (int i = 0; i<size; i++) {
            char index = x[i] - 'a';
            //該字符在當(dāng)前分支下的映射為空，沒有那就new
            if (cur->arr[index] == nullptr) {
                cur->arr[index] = new Node;
            }
            cur->arr[index]->pass++; //不管 cur->arr[index] 是new的還是本來就有，insert要路過他了，他的pass+1,
            cur = cur->arr[index];//同時cur下指過去，進(jìn)行下一個字符的insert
        }
        cur->end++;//insert最終將完整字符串個數(shù)end+1
    }

  //查找 完全匹配字符串 x 的數(shù)量 -->end
    int Find(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            //搜索到某個字符斷了，沒有這個完整的字符串x 返回0
            if (cur->arr[index] == nullptr) return 0;
            //沒斷，繼續(xù)向下一個字符搜索;
            cur = cur->arr[index];
        }
        return cur -> end;//返回完整字符串x的有效個數(shù)end
    }

//查找 前綴為字符串 x 的數(shù)量 -->pass
    int FindContain(const string& x)
    {
        //與Find一模一樣的邏輯，只是最后的return 變了，這體現(xiàn)了Node*封裝 int end  和int pass的好處了吧
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            if (cur->arr[index] == nullptr) return 0;
            cur = cur->arr[index];
        }
        return cur -> pass;
    }

 //刪掉某個完整單詞-以及這個單詞后面可能存在的所有路徑;（end>1 出現(xiàn)了很多次時，只需要end--一下）
    bool Delete(const string &x)
    {
        if (Find(x) == 0) return false;//壓根沒這個單詞，刪除失敗;
        //有這個單詞，我們需要找到他的prev前一個，delete掉他,prev的arr[x]=nullptr!
        Node* cur = root;
        Node* prev = root;
        int size = x.size();
        for (int i = 0; i < size; i++) {
            char index = x[i]-'a';
            //if (cur->arr[index] == nullptr) return false;這句不需要，都過了Find 肯定x每個字符都存在于字典樹中
            cur->pass--;//別忘了路過的路徑都得-1;
            prev = cur;
            cur = cur->arr[index];
        }
        if (cur->end==1) {//代表x所在字符串的個數(shù)只有1，直接遞歸delete刪掉它 和 他后面的子串
            delete cur;//這個delete調(diào)析構(gòu)，我們析構(gòu)已經(jīng)寫好了，防止內(nèi)存泄漏;
            prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一個字符-'a'] = nullptr!
        }
        else  cur->end--;//end>1 :end--代表這個節(jié)點(diǎn)的有效字符串個數(shù)-1，end==1 end-- == 0，這個節(jié)點(diǎn)的字符有效個數(shù)為0了，但是他因?yàn)閜ass>1,暫時保存 后面的不刪;
        //end>1,那就end有效個數(shù)-1就行了;
        return true;
    }

#include <iostream>
#include <vector>
#include <string>
using namespace std;
//26 個小寫英文字母
#define NUM 26
//前綴樹節(jié)點(diǎn)
class Node {
public:
    Node* arr[NUM];//多叉樹(最大26個分支，因?yàn)?6個小寫字母嘛)
    int end;  //代表
    int pass; //代表以此前綴為公共前綴的節(jié)點(diǎn)個數(shù),每次insert的時候會調(diào)整
    Node()
    {
        end = 0;
        pass = 0;
        memset(arr, 0, sizeof(arr));
    }
    ~Node()
    {
        //這里有點(diǎn)遞歸的意思，除了刪除當(dāng)前節(jié)點(diǎn)，更重要的是如果當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)還有非空。遞歸delete掉！
        for (int i = 0; i < NUM; i++)
        {
            if (arr[i]!=nullptr) delete arr[i];
        }
    }
};
//前綴樹主體
class Trie{
public:
    Node* root = nullptr;
public:
    Trie() {
        root = new Node;
    }
    //插入單詞
    void Insert(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        cur->pass++;//不管insert啥，我們root空節(jié)點(diǎn)的pass相當(dāng)于必須+1，最終這個root->pass可以代表一共insert了幾次=-=
        for (int i = 0; i<size; i++) {
            char index = x[i] - 'a';
            //該字符在當(dāng)前分支下的映射為空，沒有那就new
            if (cur->arr[index] == nullptr) {
                cur->arr[index] = new Node;
            }
            cur->arr[index]->pass++; //不管 cur->arr[index] 是new的還是本來就有，insert要路過他了，他的pass+1,
            cur = cur->arr[index];//同時cur下指過去，進(jìn)行下一個字符的insert
        }
        cur->end++;//insert最終將完整字符串個數(shù)end+1
    }
    //查找 完全匹配字符串 x 的數(shù)量 -->end
    int Find(const string &x)
    {
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            //搜索到某個字符斷了，沒有這個完整的字符串x 返回0
            if (cur->arr[index] == nullptr) return 0;
            //沒斷，繼續(xù)向下一個字符搜索;
            cur = cur->arr[index];
        }
        return cur -> end;//返回完整字符串x的有效個數(shù)end
    }
    //查找 前綴為字符串 x 的數(shù)量 -->pass
    int FindContain(const string& x)
    {
        //與Find一模一樣的邏輯，只是最后的return 變了，這體現(xiàn)了Node*封裝 int end  和int pass的好處了吧
        int size = x.size();
        Node* cur = root;
        for (int i = 0; i < size; i++) {
            char index = x[i] - 'a';
            if (cur->arr[index] == nullptr) return 0;
            cur = cur->arr[index];
        }
        return cur -> pass;
    }
    //刪掉某個完整單詞-以及這個單詞后面可能存在的所有路徑;（end>1 出現(xiàn)了很多次時，只需要end--一下）
    bool Delete(const string &x)
    {
        if (Find(x) == 0) return false;//壓根沒這個單詞，刪除失敗;
        //有這個單詞，我們需要找到他的prev前一個，delete掉他,prev的arr[x]=nullptr!
        Node* cur = root;
        Node* prev = root;
        int size = x.size();
        for (int i = 0; i < size; i++) {
            char index = x[i]-'a';
            //if (cur->arr[index] == nullptr) return false;這句不需要，都過了Find 肯定x每個字符都存在于字典樹中
            cur->pass--;//別忘了路過的路徑都得-1;
            prev = cur;
            cur = cur->arr[index];
        }
        if (cur->end==1) {//代表x所在字符串的個數(shù)只有1，直接遞歸delete刪掉它 和 他后面的子串
            delete cur;//這個delete調(diào)析構(gòu)，我們析構(gòu)已經(jīng)寫好了，防止內(nèi)存泄漏;
            prev->arr[x[size - 1]-'a'] = nullptr; // prev的arr[x最后一個字符-'a'] = nullptr!
        }
        else  cur->end--;//end>1 :end--代表這個節(jié)點(diǎn)的有效字符串個數(shù)-1，end==1 end-- == 0，這個節(jié)點(diǎn)的字符有效個數(shù)為0了，但是他因?yàn)閜ass>1,暫時保存 后面的不刪;
        //end>1,那就end有效個數(shù)-1就行了;
        return true;
    }
};