【数据结构与算法】字典树/前缀树（Python/C++）

字典树/前缀树 Trie

前缀树是一种树结构，当一系列单词有很多公共前缀时就可以用前缀树来存储和查询，如果这些单词没有公共前缀，那么和用数组存是一样的。因为前缀树中节点通常用字典（Python中的dict，C++中的map）这个数据结构来存储子节点，所以常被称为字典树。前缀树是一种空间换时间的思想，这个和哈希表还有动态规划是一样的。

前缀树常常被用于基于前缀的模糊匹配，但其不局限于存储单词，树中的节点可以是任意的数据类型或者结构，比如前缀树会被用来解决最大异或值的问题，这时前缀树为二叉树，节点的值为0或者1。

前缀树只能用作基于前缀的模糊匹配，如果要做到匹配字符串中的某一段则要借助基于前缀树的AC自动机了，AC自动机融合了前缀树和KMP算法的思想。

前缀树的实现（Python）

class TrieNode:
    """前缀树中节点的数据结构"""
    def __init__(self):
        # count表示有多少个单词以当前节点为结尾
        self.count      = 0
        # pre_count表示以根节点到当前节点为前缀的单词个数
        self.pre_count  = 0
        # children存储所有当前节点的下一个节点
        self.children   = {}


class Trie:
    """前缀树的实现"""
    def __init__(self):
        # 定义前缀树的根节点
        self.root = TrieNode()

    def insert(self, word):
        """向前缀树中添加单词"""
        node = self.root
        for ch in word:
            if ch not in node.children:
                node.children[ch] = TrieNode()
            node = node.children[ch]
            node.pre_count += 1
        node.count += 1

    def search(self, word):
        """查找word是否位于前缀树内"""
        node = self.root
        for ch in word:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.count > 0

    def start_with(self, prefix):
        """判断prefix是否为前缀树中的前缀"""
        node = self.root
        for ch in prefix:
            if ch not in node.children:
                return False
            node = node.children[ch]
        return node.pre_count > 0

前缀树的实现（C++类模版+智能指针）

一共有三个文件组成：main.cpp、Trie.hpp、Trie.tpp。
main.cpp：测试代码
Trie.hpp：Trie类模版的声明
Trie.tpp：Trie方法的实现，我们可以看到文件后缀不是平常的.cpp，这是因为g++编译器不支持模版的分离编译，因为编译器编译时会根据模版的类型生成对应版本的类声明，但是此时在.cpp中找不到对应类型的类方法的实现。所以这里把模版类的方法定义在单独的一个.tpp文件中，其实后缀不一定要是tpp，可以随意起一个后缀，反正要在.hpp文件后#include这个文件。其实模版类方法的实现也可以直接放在.hpp文件中，但是一般非inline函数不会在头文件里定义，所以前面那种方法更好。还有一种不好的办法是在.cpp中函数定义的下面显性声明对应类型版本的模版类，但这和我们用模版的初衷相悖，所以基本不会这样做。
这里为了避免内存泄漏和主动释放动态分配内存，运用了智能指针（smart pointer）shared_ptr来指向前缀树节点

//
//  Trie.hpp
//
//  Created by @YangZai on 26.05.21.
//
#ifndef Trie_hpp
#define Trie_hpp

// 要用智能指针须导入memory
#include <memory>
#include <map>

using namespace std;

template <typename T> struct TrieNode {
    int count;
    int pre_count;
    map<T, shared_ptr<TrieNode>> children;
};

template <typename N, typename M> class Trie {
private:
    shared_ptr<TrieNode<N>> root = make_shared<TrieNode<N>>();
public:
    void insert(M&);
    bool search(M&);
    bool startWith(M&);
};

#include "Trie.tpp"

#endif /* Trie_hpp */

//
//  Trie.tpp
template <typename N, typename M>
void Trie<N, M>::insert(M &word)
{
    auto node = root;
    for (auto &ch: word) {
        if (node->children.find(ch) == node->children.end()) {
            node->children.insert(make_pair(ch, make_shared<TrieNode<N>>()));
        }
        node = node->children[ch];
        node->pre_count++;
    }
    node->count++;
}

template <typename N, typename M>
bool Trie<N, M>::search(M &word) 
{
    auto node = root;
    for (auto &ch: word) {
        if (node->children.find(ch) == node->children.end()) {
            return false;
        }
        node = node->children[ch];
    }
    return node->count > 0;
}

template <typename N, typename M>
bool Trie<N, M>::startWith(M &prefix) 
{
    auto node = root;
    for (auto &ch: prefix) {
        if (node->children.find(ch) == node->children.end()) {
            return false;
        }
        node = node->children[ch];
    }
    return node->pre_count > 0;
}

//
//  main.cpp
//
//  Created by @YangZai on 26.05.21.
//
#include "Trie.hpp"

#include <iostream>
#include <vector>

void test_string() 
{
    cout << "N: char, M: string:" << endl;
    
    vector<string> list = {"hello world!", "hello"};
    string a = "hello";
    Trie<char, string> trie;
    for (auto &i: list) {
        trie.insert(i);
    }
    cout << "\ta" << (trie.search(a) ? " is" : " isn't") << " in the Trie"  << endl;
    cout << "\ta" << (trie.startWith(a) ? " is" : " isn't") << " one prefix in the Trie"  << endl;
}

void test_vector() 
{
    cout << "N: int, M: vector<int>:" << endl;
    
    vector<vector<int>> list = {{6, 5, 4, 3, 2, 1}, {6, 5, 4}};
    vector<int> a = {6, 5, 4};
    Trie<int, vector<int>> trie;
    for (auto &i: list) {
        trie.insert(i);
    }
    cout << "\ta" << (trie.search(a) ? " is" : " isn't") << " in the Trie"  << endl;
    cout << "\ta" << (trie.startWith(a) ? " is" : " isn't") << " one prefix in the Trie"  << endl;
}

int main(int argc, const char * argv[]) 
{
    test_string();
    test_vector();
    return 0;
}
/*
N: char, M: string:
    a is in the Trie
    a is one prefix in the Trie
N: int, M: vector<int>:
    a is in the Trie
    a is one prefix in the Trie
*/

Trie相关题目（持续更新中）