前缀树

#include <iostream>
#include <vector>
#include <string>
#include <memory>
#include <unordered_map>
using namespace std;

class TrieNode
{
public:
    int pass;
    int end;

    // 当字符种类非常多的时候（例如java中有六万多字符）
    // 这个时候再去采用定长的数组显然不合适
    // 可以采用hashmap来存放字符和node
    // unordered_map<char, shared_ptr<TrieNode>> nexts;
    vector<shared_ptr<TrieNode>> nexts;

public:
    TrieNode()
    {
        pass = 0;
        end = 0;
        // nexts[0] == nullptr,  没有走向'a'的路
        // nexts[0] != nullptr,  有走向'a'的路
        // ...
        // nexts[25] != nullptr
        nexts.resize(26, nullptr);
    }
    ~TrieNode()
    {
        nexts.clear();
    }
};

class Trie
{
public:
    shared_ptr<TrieNode> root;
    Trie()
    {
        root = make_shared<TrieNode>();
    }
    void insert(string word)
    {
        TrieNode *node = root.get();
        node->pass++;
        int index = 0;
        for (int i = 0; i < word.length(); i++)
        {
            index = word[i] - 'a';
            if (node->nexts[index] == nullptr)
            {
                node->nexts[index] = make_shared<TrieNode>();
            }
            node = node->nexts[index].get();
            node->pass++;
        }
        node->end++;
    }

    // word这个单词之前加入过几次
    int search(string word)
    {
        TrieNode *node = root.get();
        int index = 0;
        for (int i = 0; i < word.length(); i++)
        {
            index = word[i] - 'a';
            if (node->nexts[index] == nullptr)
            {
                return 0;
            }
            node = node->nexts[index].get();
        }
        return node->end;
    }

    // 删除一个单词
    void deleteWord(string word)
    {
        if (search(word) != 0)
        {
            TrieNode *node = root.get();
            node->pass--;
            int index = 0;
            for (int i = 0; i < word.length(); i++)
            {
                index = word[i] - 'a';
                if (--node->nexts[index].get()->pass == 0)
                {
                    // 从当前已知p节点遍历到底去析构
                    shared_ptr<TrieNode> cur = node->nexts[index];
                    node->nexts[index].reset();
                    node->nexts[index] = nullptr;
                    i++;
                    while (node != nullptr && i < word.length())
                    {
                        node = cur->nexts[word[i] - 'a'].get();
                        node->nexts[index].reset();
                        node->nexts[index] = nullptr;
                        cur = cur->nexts[word[++i] - 'a'];
                    }
                    return;
                }
                node = node->nexts[index].get();
            }
        }
    }

    // 所有加入的字符串中，有几个是以pre这个字符串作为前缀的
    int prefixNumber(string pre)
    {
        TrieNode *node = root.get();
        int index = 0;
        for (int i = 0; i < pre.length(); i++)
        {
            index = pre[index] - 'a';
            if (node->nexts[index] == nullptr)
            {
                return 0;
            }
            node = node->nexts[index].get();
        }
        return node->pass;
    }
};

int main()
{
    Trie t;
    t.insert("abc");

    return 0;
}