## HDU 1251 解题报告

http://acm.hdu.edu.cn/showproblem.php?pid=1251

## 统计难题

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)

### Problem Description

Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).

### Sample Input

```banana
band
bee
absolute
acm
ba
b
band
abc
```

```2
3
1
```

### CODE

```#include
#include
struct trie
{
int cnt;
trie *node[26];
trie()
{
cnt=1;
for(int i=0;i<26;++i)
node[i]=NULL;
}
} *root;
void insert(char *s)
{
int i,c;
trie *p=root;
for(i=0;s[i];++i)
{
c=s[i]-'a';
if(p->node[c])
p->node[c]->cnt++;
else
p->node[c]=new trie();
p=p->node[c];
}
}
int find(char *s)
{
int i,c;
trie *p=root;
for(i=0;s[i];++i)
{
c=s[i]-'a';
if(p->node[c])
p=p->node[c];
else
return 0;
}
return p->cnt;
}
void release(trie *p)
{
for(int i=0;i<26;++i)
if(p->node[i]) release(p->node[i]);
delete(p);
}
int main()
{
root=new trie();
char s[15];
while(gets(s))
{
if(strlen(s)>0)
insert(s);
else
break;
}
while(gets(s))
printf("%dn",find(s));
release(root);
return 0;
}
```