743
HDU1251-統計難題
統計難題
Time Limit 40002000 MS (JavaOthers) Memory Limit 13107065535 K (JavaOthers)
Total Submission(s) 16484 Accepted Submission(s) 7087
Problem Description
Ignatius最近遇到一個難題,老師交給他很多單詞(隻有小寫字母組成,不會有重複的單詞出現),現在老師要他統計出以某個字符串為前綴的單詞
數量(單詞本身也是自己的前綴).
Input
輸入數據的第一部分是一張單詞表,每行一個單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統計的單詞,一個空行代表單詞表的結
束.第二部分是一連串的提問,每行一個提問,每個提問都是一個字符串.
注意本題隻有一組測試數據,處理到文件結束.
Output
對於每個提問,給出以該字符串為前綴的單詞的數量.
Sample Input
banana
band
bee
absolute
acm
ba
b
band
abc
Sample Output
2
3
1
0
Author
Ignatius.L
字典樹訓練（今天剛學，多寫幾題練練手^_^）
AC代碼：
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
char s[20];
struct node
{
node *next[26];
int count;
node(){
memset(next,0,sizeof(next));
count=0;
}
};
node *root=new node();
void insert(char *s)
{
node *p=root;
int i,k;
for(i=0;s[i];i++)
{
k=s[i]-'a';
if(p->next[k]==NULL) p->next[k]=new node();
p=p->next[k];
p->count++;
}
}
int found(char *s)
{
node *p=root;
int i,k;
for(i=0;s[i];i++)
{
k=s[i]-'a';
if(p->next[k]==NULL) return 0;
p=p->next[k];
}
return p->count;
}
int main()
{
int i,j,n,m;
while(gets(s), strcmp(s, ""))
{
insert(s);
}
while(gets(s))
{
printf("%d\n",found(s));
}
return 0;
}
最後更新：2017-04-03 12:56:30