hdu1251+字典树常用模板

这里只简单给出几个常用的字典树的模板，要看具体介绍的请看：传送门

Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

 

Input

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

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

 

Output

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

 

Sample Input

banana

band

bee

absolute

acm

 

ba

b

band

abc

 

Sample Output

2

3

1

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
char ch[15];
int tri[maxn][30];
int sum[maxn];
void insert(char * ch,int & cnt){
	int len=strlen(ch);
	int id=0;
	for(int i=0;i<len;i++){
		int tem=ch[i]-'a';
		if(tri[id][tem]==0){
			tri[id][tem]=++cnt;
		}

		id=tri[id][tem];sum[id]++;
	}
	return ;
}
int find(char * ch){
	int len=strlen(ch);
	int id=0;
	for(int i=0;i<len;i++){
		int tem=ch[i]-'a';
		if(tri[id][tem]==0){
			return 0;
		}
		id=tri[id][tem];
	}
	return sum[id];
}
int main(){
	char ch1;
	int len=0;
	int cnt=0;
	while(ch1=getchar()){
		if(ch1!='\n')
		ch[len++]=ch1;
		if(ch1=='\n'){
			if(len==0)break;

			ch[len]='\0';
		//	puts(ch);
			insert(ch,cnt);
			len=0;
		}
	}
	while(scanf("%s",ch)!=EOF){
		//cout<<ch<<endl;
		printf("%d\n",find(ch));
	}
	return 0;
}

　　建字典树：

void insert(char * ch,int & cnt){
	int len=strlen(ch);
	int id=0;
	for(int i=0;i<len;i++){
		int tem=ch[i]-'a';
		if(tri[id][tem]==0){
			tri[id][tem]=++cnt;
		}
		id=tri[id][tem];
		sum[id]++;//可以用来查询以某字符串为前缀的字符串的数量 如hdu1251
	}
	vis[id]=1;//可以用来查询某字符串是否存在
	return ;
}

　　查询：

int find(char * ch){
	int len=strlen(ch);
	int id=0;
	for(int i=0;i<len;i++){
		int tem=ch[i]-'a';
		if(tri[id][tem]==0){
			return 0;
		}
		id=tri[id][tem];
	}
//	return vis[id];
	return sum[id];//也可以返回vis【id】，即判断当前字符串是否存在，存在返回一，不存在返回零
}