HDU-1251-统计难题
HDU-1251-统计难题
http://acm.hdu.edu.cn/showproblem.php?pid=1251
基本的字典树，字典树又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来节约存储空间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
如上图所示，每一个红色节点都一个单词，白色节点表示公共前缀
#include<iostream>#include<cstdio>#include<cstring>#include<cstdlib>using namespace std;struct node{int count;node *childs[26];node(){count=0;int i;for(i=0;i<26;i++)childs[i]=NULL;}};node *root=new node;node *current,*newnode;void insert(char *str){int i,m; current=root;for(i=0;i<strlen(str);i++){m=str[i]-'a';if(current->childs[m]!=NULL){current=current->childs[m];++(current->count);}else{newnode=new node;++(newnode->count);current->childs[m]=newnode;current=newnode;}}}int search(char *str){int i,m; current=root;for(i=0;i<strlen(str);i++){ m=str[i]-'a';if(current->childs[m]==NULL)return 0;current=current->childs[m];}return current->count;}int main(){char str[20];while(gets(str),strcmp(str,""))insert(str);while(gets(str)!=NULL)printf("%d\n",search(str));return 0;}