前缀树
标签: 机试攻略 - 高分篇
学习人数: 20.5k


高清播放
赞赏支持

定义

又称单词查找树,Trie树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计,排序和保存大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来减少查询时间,最大限度地减少无谓的字符串比较,查询效率比哈希树高。

 

考点分析

1、n个字符串中找到某个字符串是否存在或出现了几次。
解法:数据小直接顺序查找比较,数据大的时候可以直接用map来查找,如果只能用C语言,那么就需要用前缀树来解决。
2、n个字符串中查找包含某个前缀的的字符串的个数。
解法:这是非常典型的应用方法,建立前缀树即可知道每个前缀的单词个数。


 

前缀字符串
题目描述:
如果一个字符串s1是由另一个字符串s2的前面部分连续字符组成的,那么我们就说s1就是s2的前缀。比如“ac”是“acm”的前缀,“abcd”是“abcddfasf”的前缀,特别的“kdfa”是“kdfa”的前缀。 现在给你一些字符串,你的任务就是从这些字符串中找出一些字符串放到一个集合中,使得这个集合中任意一个字符串不是其他字符串的前缀,并且要使集合里的字符串尽可能的多。输出这个集合中字符串的个数。
输入描述:
有多组测试数据。每组测试数据以一个整数n开头,随后有n个字符串。 当n=0时表示输入结束。
0<n<100,字符串长度不大于20。
输出描述:
每组测试数据输出一个整数,即所求的最大值。每组数据占一行。
输入样例#:
6
acm
yuou
yuoufsdaf
acmmmdf
acmm
fdsf
0
输出样例#:
3
题目来源:
DreamJudge 1098

题目解析:这道题的数据很小,所以各种办法都可以解决,如果题目的数据大一些,比如有10W个字符串的时候,这个时候就需要用前缀树来解决了,其实这个题就是求前缀树的叶子结点的个数,因为只有是叶子结点才不会是其他字符串的前缀。


参考代码

#include <bits/stdc++.h>  
using namespace std;  
  
const int maxn = 26;//26个字母,如果包含大小写的话改成52  
typedef struct TrieNode {  
    int nCount;//结点出现次数  
    struct TrieNode *next[maxn];  
}Trie;  
Trie root;  
//初始化  
void InitTrie() {  
    for (int i = 0; i < maxn; i++)  
        root.next[i] = NULL;  
}  
//创建Trie树  
void CreateTrie(char *str) {  
    int len = strlen(str);  
    Trie *p = &root, *q;  
    for (int i = 0; i < len; i++) {  
        int k = str[i] - 'a';  
        if (p->nex...
登录查看完整内容


课后作业

掌握前缀树


登录后开始许愿

暂无评论,来抢沙发