字典树是一个数据结构，可以在log复杂度下进行前缀匹配、字符串检索等操作。

实现

我们这里采用动态开辟结点的方法实现。

如图所示，从根结点到叶子节点的路径，构成了一个个字符串。配合结束标记使用，就可以查询某个字符串是否在字典内出现过。

字典树的两个主要操作是插入和查询。

struct trie
{
    int node[500005][26]={0};//字典树的节点
    int cnt = 0;//节点个数
    int fin[500005][26] = {0};//字符串结束标记
    void insert(string s)//将一个字符串插入字典树
    {
        int t = 0;
        for(int i=0;i<s.size();i++)
        {
            if(node[t][s[i]-'a']==0)
            {
                node[t][s[i] - 'a'] = ++cnt;

            }
            if (i == s.size() - 1) fin[t][s[i] - 'a'] = 1;
            t = node[t][s[i] - 'a'];
        }
    }
    bool check(string s)//查询字符是否在字典树中，适当修改可以变成前缀查询
    {
        int t = 0;
        for(int i=0;i<s.size();i++)
        {
            if (node[t][s[i] - 'a'] != 0)
            {
                if (i == s.size() - 1 && fin[t][s[i] - 'a'] == 1) return 1;
                else if (s.size() - 1 == i) return 0;
                t = node[t][s[i] - 'a'];
            }
            else return 0;
        }
        return 1;
    }
};