统计难题 HDU – 1251(迷之测试数据)

作者: zqqian 分类: ACM 发布时间: 2017-10-09 20:18
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

 

Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

 

Output
对于每个提问,给出以该字符串为前缀的单词的数量.

 

Sample Input
banana band bee absolute acm ba b band abc

 

Sample Output
2 3 1 0
这个题就是trie树的模板题,但是一个迷之现象是用G++提交会MLE,C++就会AC,也不知道是什么原因。。。
#include <iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
using namespace std;
struct node {
	int n ;
	node *w[28];
	node(){
		n=0;
		for(int i=0;i<28;i++){
		w[i]=NULL;
		}
	}

};
node head;

void build(char a[], int len) {
	node *p = &head;

	for (int i = 0; i < len; ++i) {
		if((p->w[a[i] - 'a']) != NULL) {

			p = p->w[a[i] - 'a'];
			p->n++;
		} else {
			node *q=new(malloc(sizeof(node)))node;
			p->w[a[i] - 'a'] = q;
			p = q;
			p->n++;
		}
	}


}

int query(char a[], int len){
	node *p=&head;
for (int i = 0; i < len; ++i)
{
	if((p->w[a[i]-'a'])!=NULL){
		p = p->w[a[i] - 'a'];

	}else{
		return 0;
	}
}
return p->n;


}




int main(int argc, char const *argv[]) {
char c[101];
int mode=0;
while(gets(c)&&strlen(c)){
	build(c,(int)strlen(c));

}
while(gets(c)){
	cout<<query(c,(int)strlen(c))<<endl;
}

	return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注