1123: 统计难题
时间限制: 1 Sec 内存限制: 128 MB 提交: 4 解决: 4 [ ][ ][ ]题目描写叙述
Ignatius近期遇到一个难题,老师交给他非常多单词(仅仅有小写字母组成,不会有反复的单词出现),如今老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
输入
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每一个提问都是一个字符串.
注意:本题仅仅有一组測试数据,处理到文件结束.输出
对于每一个提问,给出以该字符串为前缀的单词的数量.
例子输入
bananabandbeeabsoluteacmbabbandabc
例子输出
2310
字典树的基础题，已经做了好几个字典树的题，思路也比較清晰，先建立字典树。然后再统计前面的前缀数目。这个题就是输入的格式要注意一下，其它的都比較简单，属于字典的入门题吧。直接用自己曾经的模板；
以下是ac的代码：
#include <cstdio> #include <cstring> #include <cstdlib> typedef struct node //节点的结构体 { int count; //计数 struct node * next[26]; }node; node * newnode() //创建新节点 { node *q; q=(node*) malloc ( sizeof (node)); q->count=1; for ( int i=0;i<26;i++) q->next[i]=NULL; return q; } void build(node *T, char *s) //建立字典树 { node *p; p=T; int len,k; len= strlen (s); for ( int i=0;i<len;i++) { k=s[i]- 'a' ; if (p->next[k]==NULL) { p->next[k]=newnode(); p=p->next[k]; } else { p=p->next[k]; p->count++; } } } int search(node *T, char *c) //查询字典树 { node *q; int sum=0,len,k; q=T; len= strlen (c); for ( int i=0;i<len;i++) { k=c[i]- 'a' ; if (q->next[k]!=NULL) q=q->next[k]; else return sum=0; } sum=q->count; return sum; } int main() { char s[12]; char c[12]; node *T; T=(node *) malloc ( sizeof (node)); T->count=0; for ( int i=0;i<26;i++) T->next[i]=NULL; memset (s,0, sizeof (s)); memset (c,0, sizeof (c)); while ( gets (s)) //控制输入这里要注意 { if ( strcmp (s, "" )==0) break ; build(T,s); } while ( scanf ( "%s" ,c)!=EOF) { printf ( "%d\n" ,search(T,c)); } return 0; }