字典树 - 暮无雪代码博客

如上图

根节点什么都不存

其余结点存各自对应的一个字符

从根节点往下遍历，遍历的字符组成了存储的字符串

建树

$next[i][c]$表示字符串与之对应的($s[j]=c$)下一个字符($s[j+1]$)存储的位置，idx用来给新的字符开辟新的空间

int next[MAX_N * 50][26], idx;

补：
inline int get_num(char ch) { return ch - 'a'; }

插入字符串

$c=get_num(s[i])$代表获取字符$s[i]$的ASCII码，$next[p][c]$代表下一个字符在next中的位置，这个$for$循环是用来迭代字符串$s$的，而$p=next[p][c]$是用来迭代字典树的。如果$next[p][c]$为$0$(初始值是$0$)，那么说明这个字符在字典树这个位置第一次出现给它开辟一个新的空间

inline void insert(const char* s) noexcept {
  int p = 0, c;
  for (int i = 0; s[i] != '\0'; ++i) {
    c = get_num(s[i]);
    if (!next[p][c]) next[p][c] = ++idx;
    p = next[p][c];
  }
  exit[p] = true;
}

查找字符串

与插入原理相同，当$next[p][c]$为0说明在字典树中以$s[0]->s[i-1]$为前缀的子串第一次出现$s[i]$，说明没找到。

inline int find(const char* s) {
  int p = 0;
  for (int i = 0; s[i] != '\0'; ++i) {
    int cn = get_num(s[i]);
    if (!next[p][cn]) return 0;
    p = next[p][cn];
  }
  //找到了，返回需要的东西
}

记录字符串第一次出现的索引

声明一个变量数组$cnts[MAXN]$每当第一次插入的时候使其值$+1$

记录字符串重复的次数

当遍历到$s[i]=='\0'$是如果$idx$没变让$++cnts[p]$

字典树数组开辟空间的大小

字典树的深度(高度)与所包含的字符串前缀的相似度有关，设每层的结点数目为$x$个，设字符串的长度最多$m$，共$n$个字符串。那么第一层就是一个，第二层为$x^2$，第三层为$x^3$·····依次类推那么，前缀相同且长度为$k$时，字典树所含有的结点的个数为$\sum^{k}_{i=0}{x^i}+(m-k)\cdot{n}$。其中$(m-k)\cdot{n}$为前缀不同剩余得结点数量的最大值，显然一般是比这个小的。以上公式前面是一个等比级数，得：

$\frac{w^{k+1}-1}{w-1} + (m-k)\cdot{n} = (1-k)\cdot{n}+n\cdot{m} \leq m\cdot{n}$。

题目

1
2
3