Trie树的作用
高效存储的查找字符串
图片来自ACwing(算法学习网) 文中左边是输入的数据 右边是建好的树
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] ++ ; }
trie树的插入代码
p表示的是层数 for (int i = 0; str[i]; i ++ ) 遍历每一个字符 int u = str[i] - ‘a’; 将字符转换成数字 当作数组下标处理
if (!son[p][u]) son[p][u] = ++ idx;
///idx表示的是用到了哪个位置 以免数组重复使用
如果数组son[p][u] 没有用过 那么就令son[p][u] = ++idx 表示用过了
如果当前位置已经存在了字符也就是son[p][u] == true
那么我们只需要继续往下一层遍历就行 p = son[p][u]
因为这个模板是统计字符出现的次数 所以cnt[p]++ 打了个记数标记
trie树查询出现次数
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]; }
如同插入一样 都是直接遍历 如果！ son[p][u]表示并没有这个字符串出现过 如果能找到最后一层那么直接返回前面打的标记就行
字符串统计题目传送门 练手的洛谷水题
