#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int const N= 1000000;
struct Trie{
int id; // 标记每一个单词
int cnt; // 标记单词前缀的数量
int next[26]; // 26 个孩子结点
void init(){
id= 0; cnt= 0;
for( int i= 0; i< 26; ++i ) next= 0;
}
};
Trie tree[N];
int num= 0, root= 0, cid= 0;
void insert( char* s ){
int rt= root;
while( *s ){
int t= *s- 'a';
if( tree[rt].next[t]== 0 ){
tree[++num].init();
tree[rt].next[t]= num;
}
rt= tree[rt].next[t];
tree[rt].cnt++;
s++;
}
tree[rt].id= ++cid;
}
int find( char* s ){
int rt= root;
while( *s ){
int t= *s- 'a';
rt= tree[rt].next[t];
if( rt== 0 ) return 0;
s++;
}
return tree[rt].cnt;
}
int main(){
char str[100];
while( gets(str)!= NULL ){
if( strlen(str)== 0 ) break;
insert( str );
}
while( gets(str)!= NULL )
printf("%d\n", find(str) );
return 0;
}
Another implement: http://www.cnblogs.com/Xredman/archive/2009/04/10/1433167.html
分享到:
相关推荐
Trie,又称为前缀树或字典树,是一种用于存储动态集合或关联数组的树形数据结构。它的主要特点是通过键的前缀来组织节点,从而快速进行前缀查询和模糊搜索。在Go语言中实现Trie,可以有效地支持字符串集合的增删查改...
**哈希 Trie 树(HashTrie)与字典树(Trie树)详解** 哈希 Trie 树,也称为 HashTrie 或者是哈希化的 Trie 树,是一种结合了哈希表和 Trie 数据结构特点的数据结构。它在 Trie 树的基础上引入了哈希函数,提高了...
本文将深入探讨“autocomplete_trie-0.1.tar.gz”这个Python库,它是一个专为实现自动补全功能的字典树结构。 标题中的“Python库 | autocomplete_trie-0.1.tar.gz”揭示了我们要讨论的主题是一个名为...
在计算机科学中,字典树(也称为前缀树或TrieTree)是一种高效的数据结构,主要用于存储字符串集合。它能够快速地进行关键词查找、插入和删除操作,尤其适合于处理大量的词汇数据,如在四六级英语考试的高频词汇查询...
这个Java程序利用了数据结构——字典树(Trie),也被称为前缀树或PAT树,它在处理字符串相关的搜索问题时表现出色。下面我们将深入探讨字典树的工作原理及其在拼写检错中的应用。 字典树是一种树形数据结构,每个...
字典树是一种树形结构,也称为单词查找树或Trie树。它是一种哈希树的变种,典型应用是用于统计、排序和保存大量的字符串(但不仅限于字符串)。字典树的优点是利用字符串的公共前缀来节约存储空间,最大限度地减少...
在IT领域,字典树(Trie,也称为前缀树或字首树)是一种非常重要的数据结构,常用于高效地存储和检索字符串。在这个场景中,标题“字典树查找统计及单词”指的是利用字典树进行单词查找、统计以及可能的分析操作。...
trie-dictionary是一个基于Patricia Radix树数据结构的实现,主要用于存储和检索字典中的单词。Patricia Radix树,也称为最小前缀树或PATRICIA树,是一种高效的空间节省的数据结构,用于存储键值对,尤其适用于字符...
Trie树(字典树)和后缀树是两种用于处理字符串问题的高级数据结构,在算法面试中是高频考点,对于程序员来说,掌握它们对于解决实际问题非常重要。Trie树适合解决单词查找以及统计问题,而后缀树则在字符串模式匹配...
首先,我们要理解Trie(字典树)的基本概念。Trie是一种树形数据结构,每个节点代表一个字符串的前缀,根节点不包含任何字符,而叶节点则表示完整的单词。通过这种结构,可以快速地进行前缀查找,因为从根节点到某个...
2. **单词搜索II**:这个题目要求在一个二维网格中找出所有符合特定模式的单词,这需要结合深度优先搜索(DFS)和字典树进行解决,展示了字典树在实际问题中的应用。 ### 5. 应用场景 - **搜索引擎**:字典树常...
在IT领域,字典树(Trie,也称为前缀树或字首树)是一种用于存储动态集合或关联数组的数据结构。它以高效的方式处理字符串查询,尤其适用于查找具有共同前缀的单词。字典树的主要优点是它可以快速地通过共享前缀来...
字典树,也被称为Trie或Prefix Tree,是一种用于存储字符串的数据结构,它在IT领域尤其是在文本处理、搜索引擎和编程语言实现中具有广泛的应用。字典树的主要特点是能够快速进行字符串的查找、插入和删除操作,尤其...
### 字典树(Trie Tree)相关知识点 #### 一、什么是字典树? 字典树,也称为前缀树或Trie树,是一种用于存储字符串的高效数据结构。它利用了字符串之间的公共前缀来减少存储空间的需求,并且能够快速进行插入、...
### 二十六叉字典树知识点详解 ...二十六叉字典树(Trie)是一种非常有用的数据结构,在处理字符串相关的应用场景中具有独特的优势。无论是从理论研究还是实际应用的角度来看,掌握Trie树的相关知识都是非常有价值的。
在字典树(Trie,也称为前缀树或数字检索树)中应用深度优先遍历,可以有效地统计单词出现的个数。字典树是一种数据结构,常用于存储大量字符串,它允许我们快速查找以特定前缀开头的所有单词。 在Java中,实现字典...
字典树,也被称为Trie或前缀树,是一种用于高效存储和检索字符串的数据结构。在C语言中实现字典树,主要涉及到链表、指针操作和动态内存分配等核心概念。以下是对字典树算法及其C语言实现的详细说明: ### 1. 字典...
字典树作为一种高效的数据结构,在文本搜索、自动补全、拼写检查等领域有着广泛的应用。通过理解其基本原理和实现模版,我们可以更灵活地运用字典树解决实际问题。希望本文能够帮助读者掌握字典树的核心概念,并鼓励...