字典树(Tire)模板

 #include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node
{
node *ne[];
int cnt;
}*head;
void insert(char *s)
{
node *p=head,*q;
for(int i=;s[i];i++)
{
int id=s[i]-'a';
if(p->ne[id]!=NULL)
{
p=p->ne[id];
p->cnt++;
}
else
{
q=(node*)malloc(sizeof(node));
for(int i=;i<;i++)
q->ne[i]=NULL;
q->cnt=;
p->ne[id]=q;
p=p->ne[id];
}
}
}
int Q(char *s)//查询有多少以该串为前缀的串的数量
{
node *p=head;
for(int i=;s[i];i++)
{
int id=s[i]-'a';
if(p->ne[id]!=NULL)
p=p->ne[id];
else
return ;
}
return p->cnt;
}
void clean(node *p)//释放空间
{
if(p==NULL) return ;
for(int i=;i<;i++)
{
if(p->ne[i]!=NULL)
clean(p->ne[i]);
}
free(p);
return ;
}
int main()
{
int n,m;
char s[];
while(scanf("%d",&n)!=EOF)
{
head=(node*)malloc(sizeof(node));
for(int i=;i<;i++)
head->ne[i]=NULL;
while(n--)
{
scanf("%s",s);
insert(s);
}
scanf("%d",&m);
while(m--)
{
scanf("%s",s);
printf("%d\n",Q(s));
}
clean(head);
}
return ;
}

hiho1014

#include<stdio.h>
#include<string.h>
const int N=1e5+;
int t[N*][],cnt;
void insert(char *s){
int now=;
for(int i=;s[i];i++){
int id=s[i]-'a';
if(!t[now][id]){
t[now][id]=++cnt;
}
now=t[now][id];
t[now][]++;
}
}
int Q(char *s){
int now=;
for(int i=;s[i];i++){
int id=s[i]-'a';
if(t[now][id])
now=t[now][id];
else
return ;
}
return t[now][];
}
int main(){
int n;
char s[];
while(scanf("%d",&n)!=EOF){
memset(t,,sizeof(t));cnt=;
while(n--){
scanf("%s",s);
insert(s);
}
scanf("%d",&n);
while(n--){
scanf("%s",s);
printf("%d\n",Q(s));
}
}
return ;
}
上一篇:每天一个Linux命令(43)at命令


下一篇:Hibernate学习笔记三