这里只简单给出几个常用的字典树的模板，要看具体介绍的请看：传送门
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】，即判断当前字符串是否存在，存在返回一，不存在返回零
}