Description
Input
Output
Sample Input
Sample Output
#include"iostream" #include"algorithm" #include"cstdio" #include"cstring" #define MX 110000 #define INF 0x3f3f3f3f #define lson l,m,rt<<1 #define rson m+1,r,rt<<1|1 using namespace std; struct Trie { int v;//v每个字母的次数; Trie *next[26]; } root; void BuildTrie(char *s) { int len=strlen(s); Trie *p=&root,*q; for(int i=0; i<len; i++) { int num=s[i]-‘a‘; if(p->next[num]==NULL) { q=(Trie *)malloc(sizeof(root));//申请一块新内存; //动态分配内存 q->v=1; for(int j=0; j<26; j++) { q->next[j]=NULL; //清空申请内存的所有子节点 } p->next[num]=q; //往子节点下去继续记录字典树 p=p->next[num]; } else { p=p->next[num]; p->v++; //如果到达此处的字典树已经存在,数加一 } } } int Query(char *s) { int len=strlen(s); Trie *p=&root; for(int i=0; i<len; i++) { int num=s[i]-‘a‘; if(p->next[num]==NULL) { return 0; }//如果后面一个节点是空的,则说明这个字符串不存在字典树中 else p=p->next[num]; //否则继续往下查询 } int v=p->v; return v; //如果查询结束,返回这个字符串出现过的次数 } int main() { char s[15]; for(int i=0; i<26; i++) root.next[i]=NULL; while(gets(s)&&s[0]!=‘\0‘) { BuildTrie(s); } while(~scanf("%s",s)) { printf("%d\n",Query(s)); } return 0; }
原文:http://www.cnblogs.com/HDMaxfun/p/5697596.html