Trie树（字典树）

作用： 高效存储和查找字符串

实现：将字符串按序排列形成树状结构，查找时就可按照类似字典查找一样的顺序查找匹配字符串因此Trie树也被称为字典树或前缀树

  1. 构造链式存储结构存储树状的Trie树
  2. 这里使用了数组模拟链表的形式 使得插入操作更简单；需要考虑的是每个节点的分叉个数即每个节点的状态数来确定每个节点的下指针域的数量
  3. 插入时，按序查找如果匹配到结尾就在结尾节点标定匹配成功标记或者设置匹配节点数量加一，如遇到查找失效则自行建立下指针直至字符结尾并设置结尾匹配成功标记
  4. 查询时只需要根据是否在匹配到字符结尾的同时匹配到字典树的结尾标定或者是在匹配过程中发现下指针指向根节点代表匹配失败

trie1

（图片引用自OI-wiki）

核心代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include<iostream>
using namespace std;

const int N = 100010;

int son[N][26], cnt[N], idx; //下标为0的点 既是根节点也是空节点

void insert(char str[]){
    int p  = 0;
    for(int i = 0; str[i]; i++){
        int u  = str[i]-'a';
        if(!son[p][u]) son[p][u] = ++idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int query(char str[]){
    int p = 0;
    for(int i = 0; str[i]; i++){
        int u = str[i] - 'a';
        if(!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

OI-wiki版的结构体封装：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
struct trie {
  int nex[100000][26], cnt;
  bool exist[100000];  // 该结点结尾的字符串是否存在

  void insert(char *s, int l) {  // 插入字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
      p = nex[p][c];
    }
    exist[p] = 1;
  }
  bool find(char *s, int l) {  // 查找字符串
    int p = 0;
    for (int i = 0; i < l; i++) {
      int c = s[i] - 'a';
      if (!nex[p][c]) return 0;
      p = nex[p][c];
    }
    return exist[p];
  }
};