ati col struct amp 单词数 absolute err next
Ignatius 最近遇到一个难题, 老师交给他很多单词 (只有小写字母组成, 不会有重复的单词出现), 现在老师要他统计出以某个字符串为前缀的单词数量 (单词本身也是自己的前缀).
Input 输入数据的第一部分是一张单词表, 每行一个单词, 单词的长度不超过 10, 它们代表的是老师交给 Ignatius 统计的单词, 一个空行代表单词表的结束. 第二部分是一连串的提问, 每行一个提问, 每个提问都是一个字符串.
注意: 本题只有一组测试数据, 处理到文件结束.
Output 对于每个提问, 给出以该字符串为前缀的单词的数量.
Sample Input
- banana
- band
- bee
- absolute
- acm
- ba
- b
- band
- abc
Sample Output
- 2
- 3
- 1
- 0
- 字典树裸题,注意没给输入大小很坑,暴力直接TLE
- #include <stdio.h>
- #include <string.h>
- #include <iostream>
- using namespace std;
- struct node{
- int num;
- node* next[26];
- node()
- {
- num=0;
- for(int i=0;i<26;i++)
- next[i]=NULL;
- }
- };
- node* root=new node();
- node* rt;
- int id,len;
- void build(char* str)
- {
- rt=root;
- len=strlen(str);
- for(int i=0;i<len;i++)
- {
- id=str[i]-'a';
- if(rt->next[id]==NULL)
- rt->next[id]=new node();
- rt=rt->next[id];
- rt->num++;
- }
- }
- int querry(char* str)
- {
- rt=root;
- len=strlen(str);
- for(int i=0;i<len;i++)
- {
- id=str[i]-'a';
- if(rt->next[id]==NULL)
- return 0;
- rt=rt->next[id];
- }
- return rt->num;
- }
- int main()
- {
- char str[15];
- while(gets(str)&&str[0])
- build(str);
- while(gets(str))
- {
- printf("%d\n",querry(str));
- }
- return 0;
- }
HDU - 1251 统计难题
来源: http://www.bubuko.com/infodetail-2278820.html