HDU-1251 统计难题,字典树或者map!

统计难题

很久就看过这个题了,但不会~~~不会~~

题意:给出一张单词表,然后下面有若干查询,每次给出一个单词,问单词表中是否存在以这个单词为前缀的单词,输出数量。本身也是自身的前缀。只有一组数据!

思路:用gets或输入字符都行。如果输入字符可以用map存图,维护每个单词的所有前缀,直接查找就行。要么就用字典树建图,路径每经过一次就加1,如果是新节点直接附为1。查找时要注意是否存在查找单词的指针,不存在或者为空直接返回0,因为没有给其赋值。空间复杂度26^i,i为单词的长度,相当于26叉树。

struct Tree
{
int f;
Tree *next[N];
};
void insert(Tree *root,char *s)
{
if(root==NULL||*s=='\0') return ;
Tree *q=root;
while(*s!='\0')
{
if(q->next[*s-'a']==NULL)//节点不存在,建立新的节点
{
Tree *temp=new Tree;
for(int i=0;i<N;i++) temp->next[i]=0;
temp->f=1;
q->next[*s-'a']=temp;
q=q->next[*s-'a'];
}
else
{
q=q->next[*s-'a'];
q->f++;
}
s++;
}
}
int query(Tree *root,char *s)
{
Tree *q=root;
while(*s!='\0'&&q!=NULL)
{
q=q->next[*s-'a'];
s++;
}
if(q==NULL) return 0;
return q->f;
}
void del(Tree *root)
{
for(int i=0;i<N;i++)
if(root->next[i]!=NULL)
del(root->next[i]);
delete(root);
}
int main()
{
char s[10];
Tree *root=new Tree;
for(int i=0;i<N;i++) root->next[i]=NULL;
while(gets(s)&&s[0])
{
insert(root,s);
}
while(gets(s))
{
printf("%d\n",query(root,s));
}
del(root);
return 0;
}

结束记得释放内存!虽然还有点没搞清~

上一篇:Unix System Overview


下一篇:Nginx+Keepalived 实现双击热备及负载均衡