# 统计难题

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

Input

Output

Sample Input
```banana
band
bee
absolute
acm

ba
b
band
abc```

Sample Output
```2
3
1
0```

```#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct Trie {
int cnt;
Trie *next[26];
}*root;
void Insert(char *s) {
Trie *p,*t;
int l=strlen(s);
p=root;
for(int i=0; i<l; i++) {
if (p->next[s[i]-'a']==NULL) {
t=new Trie;
t->cnt=1;
for (int j=0; j<26; j++)
t->next[j]=NULL;
p->next[s[i]-'a']=t;
} else
p->next[s[i]-'a']->cnt++;
p=p->next[s[i]-'a'];
}
}
int Search(char *s) {
Trie *p;
int l=strlen(s);
p=root;
for(int i=0; i<l; i++) {
if (p->next[s[i]-'a']==NULL)
return 0;
p=p->next[s[i]-'a'];
}
return p->cnt;
}
void Release(Trie *p) {
if (p==NULL)
return ;
for (int i=0; i<26; i++)
if (p->next[i] != NULL)
Release(p->next[i]);
free(p);
root = NULL;
return ;
}
void Init() {
root=new Trie;
root->cnt=0;
for (int i=0; i<26; i++)
root->next[i]=NULL;
}
int main () {
char str[15];
Init();
while (gets(str),strcmp(str,"")!=0)
Insert(str);
while (scanf ("%s",str)!=EOF)
printf ("%d\n",Search(str));
Release(root);
return 0;
}```