首页 > 其他 > 详细

ACM:统计难题 解题报告-字典树(Trie树)

时间:2016-07-23 00:30:40      阅读:326      评论:0      收藏:0      [点我收藏+]
统计难题
Time Limit:2000MS     Memory Limit:65535KB     64bit IO Format:%I64d & %I64u
Submit Status

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|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;
}

  

ACM:统计难题 解题报告-字典树(Trie树)

原文:http://www.cnblogs.com/HDMaxfun/p/5697596.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!