Trie树算法

Trie树，也称为前缀树或字典树，是一种特殊的树型数据结构。它用于存储一组字符串，使得查找、插入和删除字符串的操作非常高效。类似这种，

模板：
这是用数组来模仿上图中的树的结构，逻辑上和上图结构一致。
大家肯定要手动看代码模仿一边，只靠想象不光浪费时间还想不明确。
int son[N][26], cnt[N], idx;
// 0号点既是根节点，又是空节点，这里0号点指的是idx
// son[][]存储树中每个节点的子节点
// cnt[]存储以每个节点结尾的单词数量
// 插入一个字符串
void insert(char *str)
{
    int p = 0;
    for (int i = 0; str; i ++ )
    {
        int u = str - 'a';
        if (!son[p]) son[p] = ++ idx;
        p = son[p];
    }
    cnt[p] ++ ;
}
// 查询字符串出现的次数
int query(char *str)
{
    int p = 0;
    for (int i = 0; str; i ++ )
    {
        int u = str - 'a';
        if (!son[p]) return 0;
        p = son[p];
    }
    return cnt[p];
}

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。