统计难题
Time Limit:2000MS Memory Limit:65535KB 64bit IO Format:%I64d & %I64u Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串. 注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana band bee absolute acm ba b band abc
Sample Output
2 3 1 0
写的第一个字典树，用动态分配内存来写的，一开始用G++交了2发都是爆内存，找了半天的问题没找出来，百度了下，发现是G++在动态分配内存的时候会给指针也分配一个相同大小的内存（申请这么多次不爆掉才怪。。。。
后来用C++交了一发，AC了。
好像还能用其他的方法做这个题目，这个以后再补充。
#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|1using 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 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 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;}