字典树

介绍

Trie是一种能够快速插入和查询字符串的多叉树结构。

节点的编号各不相同，根节点编号是 $0$ ，其他节点用来标识路径，还可以标记单词插入的次数。边表示字符。

Trie维护字符串的集合，支持两种操作：

1. 向集合中插入一个字符串，void insert(char * s)
2. 在集合中查寻一个字符串，int querry(char * s)

建字典树

儿子数组 ch[p][j] 存储从节点 p 沿着 j 这条边走到的子节点。

• 边为 $26$ 个英文字母对应映射位 $0 - 25$。
• 每个节点最多会有 $26$ 个分叉。

计数数组 cnt[p] 存储以节点 p 结尾的单词的插入次数。

节点编号 idx 用来个节点编号。

1. 空 Trie 仅有一个根节点，编号为 $0$ ；
2. 从根节点开始插，枚举字符串的每个字符；
   如果没有儿子，则 p 指针走到儿子，
   如果没有儿子，则先创建儿子，p 指针再走到儿子。
3. 在单词结束点记录插入次数。

char ch[N][26] ;
int cnt [N] ;
int idx ;
char s[N] ;
void insert(char * s){
    int p = 0 ;
    for(int i = 0 ; s[i] ; ++ i){
        int j = s[i] - 'a' ;
        if(!ch[p][j]) ch[p][j] = ++ idx ;
        p = ch[p][j] ;
    }
    cnt[p] ++ ;
}

 

查询

1. 从根开始查，扫描字符串。
2. 有字母 s[i] ，则走下来，能走到词尾，则返回插入次数。
3. 无字母 s[i] ，返回 $0$ ；

int querry(char * s){
    int p = 0 ;
    for(int i = 0 ; s[i] ; ++ i){
        int j = s[i] - 'a' ;
        if(!ch[p][j]) return 0 ;//说明该单词不存在
        p = ch[p][j] ;
    }
    return cnt[p] ;
}

相关题目

E. Collapsing Strings