数据结构之trie(字典树)

解决问题

• 插入一个单词
• 从插入单词中查找该单词

$Trie是用于实现字符串快速检索的多叉树结构$

$Trie中的每一个节点都有若干个字符指针,若在检索时扫描到字符串c,就沿当前字符指针走向对应节点$

插入

void insert()
{
    int p = 0;
    for (int i = 0; str[i]; i ++ )
    {
        int ch = str[i] - 'a';
        if (!trie[p][ch])trie[p][ch] = ++ tot ;
        p = trie[p][ch];
    }
    cnt[p] ++ ;
}

查询

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