1.关于trie树：

又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高

它的原理是用空间换取时间，有下面几个特点：
1.根节点不包含字符，除根节点外每一个节点都只包含一个字符。
2.从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
3.每个节点的所有子节点包含的字符都不相同。

浅谈trie树（字典树）
从上面的图我们可以看出来
1.trie树每条边对应一个字母
2.每个节点对应一项前缀
3.int 和inn 有共同的前缀，所以共享左边的分支in

2.开始搭建树

定义一个insert函数，用来插入想要插入的单词（前缀）

void insert(string a)
{
  int h=0;
  for(int i=0;i<a.size();i++)
  {
    int id=a[i]-'a';
    if(!trie[h][id])
    trie[h][id]=++cnt;
    h=trie[h][id];
  }
}

这里要注意的是h是当前的深度，++cnt的作用是记录节点数，如果有新的节点出现就+1，每个数都对应一个节点，一个节点（h）和一个id（0-26）对应一个字母，如果发现当前的节点不是0，那么就说明这个地方和当前的字符重合了，可以直接使用使其变成公共的字符

3.寻找前缀是否存在

bool search(string a)
{
  int h=0;
  for(int i=0;i<a.size();i++)
  {
    int id=a[i]-'a';
    if(!trie[h][id])
    return 0;
    h=trie[h][id];
  }
  return 1;
}

这个就很好理解了，一个一个寻找，层层递进，如果发现找不到就直接return 0 返回false，如果可以走出for循环说明可以找到，那么就返回true

4.模版完整代码

#include<bits/stdc++.h>
using namespace std;
int trie[100010][26];
int cnt=0;
void insert(string a)
{
  int h=0;
  for(int i=0;i<a.size();i++)
  {
    int id=a[i]-'a';
    if(!trie[h][id])
    trie[h][id]=++cnt;
    h=trie[h][id];
  }
}
bool search(string a)
{
  int h=0;
  for(int i=0;i<a.size();i++)
  {
    int id=a[i]-'a';
    if(!trie[h][id])
    return 0;
    h=trie[h][id];
  }
  return 1;
}
int main()
{
    string a;
    cin>>a;
    insert(a);
    string b;
    cin>>b;
    return search(b)?cout<<"YES":cout<<"NO",0;
}

需要注意的是这个模版只能查询前缀和，并不能查询是否出现过单词

这里一道例题来用一下trie树：

HDU - 1251 统计难题

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana
band
bee
absolute
acm

ba
b
band
abc
Sample Output
2
3
1
0

这题算是直接利用了trie树的模版，加了一个sum数组来记录当前前缀出现过几次，需要注意的是判断空行用cin的话不好判断，所以用了getline 然后如果a.size()为0的话就可以进行询问输入了，代码：

#include<iostream>
using namespace std;
int trie[1000010][26];
int cnt;
int sum[1000010];

void insert(string a)
{
  int h=0;
  for(int i=0;i<a.size();i++)
  {
    int id=a[i]-'a';
    if(!trie[h][id])
    {
      trie[h][id]=++cnt;
    }
    h=trie[h][id];
    sum[h]++;
  }
  //cout<<a<<endl;
}

int search(string a)
{
  int h=0;
  for(int i=0;i<a.size();i++)
  {
    int id=a[i]-'a';
    if(!trie[h][id])
    return 0;
    h=trie[h][id];
  }
  return sum[h];
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  string a;
  while(getline(cin,a))
  {
    if(!a.size())
    break;
    insert(a);
  }
  string b;
  while(cin>>b)
  {
    cout<<search(b)<<endl;
  }
}

这里再贴一个元哥（大佬）的模版，用的是构造函数感谢元哥的帮助！

1.初始化（构造函数）

const int N = 1e6+10;
int tot = 1;
struct node
{
    int son[26];
    bool have;
    int cnt;
    node()
    {
        memset(son,0,sizeof son);
        cnt = 0;
        have = false;
    }
}trie[N];

2.insert函数

void Insert(string s)
{
    int u = 0;
    int id = 0;
    for(int i = 0;i < s.size();i++)
    {
        id = s[i]-'a';
        if(!trie[u].son[id])
            trie[u].son[id] = tot++;
        u = trie[u].son[id];
    }
    trie[u].have = true;
}

3.find1函数（寻找前缀和）

只能判断前缀不能判断自己和自己

int Find1(string s)
{
    int u = 0;
    int id = 0;
    for(int i = 0;i < s.size();i++)
    {
        id = s[i]-'a';
        if(!trie[u].son[id])
            return 0;
        u = trie[u].son[id];
    }
    bool flag = 0;
    for(int i = 0;i < 26;i++)
    {
        //int tmp = trie[u].son[i];
        if(trie[u].son[i])
            flag = 1;
    }
    if(flag)
        return 1;
    return 0;
}

4.find2函数（查询是否相等）

int Find2(string s)
{
    int u = 0;
    int id = 0;
    for(int i = 0;i < s.size();i++)
    {
        id = s[i]-'a';
        if(!trie[u].son[id])
            return 0;
        u = trie[u].son[id];
    }
    if(!trie[u].have)   // 没有这个单词
        return 0;
    if(!trie[u].cnt)   // 没被查询过
    {
        trie[u].cnt++;
        return 1;
    }
    return 0;
}

5.main函数

int main()
{
    string s,ss;
    cin>>s>>ss;
    Insert(s);
    cout<<Find1(ss)<<" "<<Find2(ss);
    return 0;
}

浅谈trie树（字典树）