首页 > 代码库 > hdu 1251 统计难题 (Trie树)
hdu 1251 统计难题 (Trie树)
本题是trie树模板题，如果不用trie而用map写可以看出trie处理这类问题有明显的时间优势。
在trie树中查找一个关键字的时间和树中包含的结点数无关，而取决于组成关键字的字符数。（对比：二叉查找树的查找时间和树中的结点数有关O(log2n)。）
如果要查找的关键字可以分解成字符序列且不是很长，利用trie树查找速度优于二叉查找树。
若关键字长度最大是5，则利用trie树，利用5次比较可以从265＝11881376个可能的关键字中检索出指定的关键字。而利用二叉查找树至少要进行log2265=23.5次比较。
//125ms#include<iostream>#include<cstdio>#include<cstdlib>#include<cstring>#include<string>#include<cmath>#include<map>#include<set>#include<vector>#include<algorithm>#include<stack>#include<queue>#include<cctype>#include<sstream>using namespace std;#define pii pair<int,int>#define LL long long intconst int eps=1e-8;const int INF=1000000000;const int maxn=1;struct trie{ trie *child[26]; int v;};trie root;void create_trie(char *ss){ int len=strlen(ss); trie *p=&root,*q; for(int i=0;i<len;i++) { int id=ss[i]-‘a‘; if(p->child[id]==NULL) { q=(trie*)malloc(sizeof(trie)); q->v=1; for(int j=0;j<26;j++) { q->child[j]=NULL; } p->child[id]=q; p=p->child[id]; } else { p->child[id]->v++; p=p->child[id]; } }}int find_trie(char*ss){ int len=strlen(ss); trie *p=&root; for(int i=0;i<len;i++) { int id=ss[i]-‘a‘; if(p->child[id]==NULL) return 0; p=p->child[id]; } return p->v;}int main(){ //freopen("in8.txt","r",stdin); char str[15]; while(gets(str)&&(str[0]!=‘\0‘)) { create_trie(str); } while(scanf("%s",str)!=EOF) { printf("%d\n",find_trie(str)); } return 0;}
//1171ms#include <iostream>#include <map>#include <cstring>#include <string>using namespace std;int main(){ int i, len; char str[10]; map<string, int> m; while( gets(str) ) { len = strlen(str); if ( !len ) { break; } for(i = len; i > 0; i--) { str[i] = ‘\0‘; m[str]++; } } while( gets(str) ) { cout << m[str] << endl; } return 0;}
hdu 1251 统计难题 (Trie树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。