Problem Description

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

 

Input

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

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

 

Output

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

 

Sample Input

 

Sample Output

对于每一个节点，从根遍历到他的过程就是一个单词，如果这个节点被标记为红色，就表示这个单词存在，否则不存在。
那么，对于一个单词，我只要顺着他从跟走到对应的节点，再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色，就相当于插入了这个单词。
这样一来我们询问和插入可以一起完成，所用时间仅仅为单词长度，在这一个样例，便是10。
们可以看到，trie树每一层的节点数是26^i级别的。所以为了节省空间。我们用动态链表，或者用数组来模拟动态。空间的花费，不会超过单词数×单词长度。

//Memory   Time

//  K      MS

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<iostream>

#include<vector>

#include<queue>

#include<stack>

#include<iomanip>

#include<string>

#include<climits>

#include<cmath>

#define MAX 1100

#define LL long long

using namespace std;

struct Node

{

    int cnt;

    bool isWord;

    Node *next[30];

    Node()

    {

        cnt=0;

        isWord=false;

        for(int i=0;i<30;i++)

            next[i]=NULL;

    }

} *root=NULL;

void Insert(char str[])

{

    if(!root)     //    第一次的时候要为root申请内存

        root=new Node;

    Node *location=root;

    int len=strlen(str);

    if(len==0)

        return ;

    for(int i=0;i<len;i++)

    {

        int num=str[i]-'a';

        if(location->next[num]!=0)  //   表示该字符已经存在

        {

            location=location->next[num];   //  直接跳到下一个字符

            location->cnt++;  //    下一个字符遍历次数+1

        }

        else

        {

            location->next[num]=new Node;

            location=location->next[num];

            location->cnt=1;

        }

    }

//    location->isWord=true;

}

int Search(char str[])

{

    Node *location=root;

    int len=strlen(str);

    if(len==0)  return 0;

    for(int i=0;i<len;i++)

    {

        int num=str[i]-'a';

        if(location->next[num]!=NULL)

            location=location->next[num];

        else       //查找的字符串长度大于字典长度

            return 0;

    }

    return location->cnt;

}

int main()

{

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

//    freopen("cout.txt","w",stdout);

     char str[30];

     while(gets(str),strcmp(str,""))

         Insert(str);

     int ans;

     while(scanf("%s",str)!=EOF)

         cout<<Search(str)<<endl;

    return 0;

}