Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量
链接:
- #include<stdio.h>
- #include<string.h>
- #include<stdlib.h>
- struct node
- {
- int count ;
- struct node *next[26];//定义26个分节点
- };
- struct node *root;
- struct node *build()//建立节点
- {
- struct node *p;
- p=(struct node *)malloc(sizeof(struct node));
- for(int i=0;i<26;i++)
- {
- p->next[i]=NULL;//令其指向0;
- }
- p->count=1;/*如果出现这个站点,那么它的次数肯定是大于等于1的。
- 但是我们刚开始建立不必考虑后续问题*/
- return p;//返回新建立的节点
- }
- void save(char *s)//储存字母
- {
- int len=strlen (s);
- if(len==0)return ;
- struct node *p;
- p=root;
- for(int i=0;i<len;i++)
- if(p->next[s[i]-'a']!=NULL)
- /*如果这个节点之前就已经存在呃,我们只需要把统计次数加上1.*/
- {
- p=p->next[s[i]-'a'];
- p->count=p->count+1;
- }
- else//如果不存在的话,我们就建立一个新的节点
- {
- p->next[s[i]-'a']=build();
- p=p->next[s[i]-'a'];
- }
- }
- int seach (char *s)//这个函数来查询数据
- {
- struct node *p;
- int len=strlen(s);
- if(len==0)return 0;
- p=root;//此处小心
- for(int i=0;i<len ;i++)
- {
- if(p->next[s[i]-'a']!=NULL)//说明还有下个节点,继续查询
- p=p->next[s[i]-'a'];
- else
- return 0;
- /*如果没有指向下个节点,说明这个要查询的字符串根本不存在,直接返回0*/
- }
- return p->count;
- }
- int main()
- {
- char str[15];
- int ans;
- root=build();
- while(gets(str)&&str[0]!='\0')//不输入直接一个Enter,那个这个字符串相当'\0';
- save(str);
- while(scanf("%s",str)!=EOF)
- {
- ans=seach(str);
- printf("%d\n",ans);
- }
- return 0;
- }
阅读(2421) | 评论(0) | 转发(0) |