Trie树的归纳(一) 之基础归纳

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]表示并没有这个字符串出现过 如果能找到最后一层那么直接返回前面打的标记就行

字符串统计题目传送门 练手的洛谷水题