Problem Description

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

 

Input

输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.

注意:本题只有一组测试数据,处理到文件结束.

 

Output

对于每个提问,给出以该字符串为前缀的单词的数量.

 

Sample Input

 

Sample Output

 

Author

Ignatius.L

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #define FOR(a,b,c) for(int a=(b);a<=(c);a++)

 using namespace std;

 const int maxnode = ;

 //输入的字符串可能很多

 const int maxl = ;

 const int sigmasize = ;

 struct Trie{

     int ch[maxnode][sigmasize];

     int tot[maxnode];

     int sz;

     Trie() {

         sz=;

         memset(ch[],,sizeof(ch[]));

         tot[]=;

     }

     int idx(char c) { return c-'a'; }

     void insert(char* s) {

         int n=strlen(s),u=;

         for(int i=;i<n;i++) {

             int c=idx(s[i]);

             if(!ch[u][c]) {

                 ch[u][c]=sz;

                 memset(ch[sz],,sizeof(ch[sz]));

                 tot[sz]=;

                 sz++;

             }

             u=ch[u][c];

             tot[u]++;

         }

     }

     int find(char* s) {

         int n=strlen(s),u=;

         for(int i=;i<n;i++) {

             int c=idx(s[i]);

             if(!ch[u][c]) return ;

             else u=ch[u][c];

         }

         return tot[u];

     }

 }trie;

 int n;

 int main() {

     //freopen("cin.in","r",stdin);

     //freopen("coutme.out","w",stdout);

     char s[maxl];

     while(gets(s) && s[]) {

         trie.insert(s);

     }

     while(gets(s)) {

         printf("%d\n",trie.find(s));

     }

     return ;

 }