统计难题

Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others) 
Total Submission(s): 42063 Accepted Submission(s): 15153

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

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

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

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

Sample Input 
banana 
band 
bee 
absolute 
acm

ba 
b 
band 
abc

Sample Output 
2 
3 
1 
0

解题思路：运用字典树给节点中放入计数器；

#include 
    
      using namespace std; const int MAX = 27; struct TrieNode{
       TrieNode* next[27];     int _n;     TrieNode()         :_n(1)     {
           for (int i = 0 ; i < MAX; ++i){
               next[i] = NULL;         }     } }; class Trie{
       typedef TrieNode Node;     typedef TrieNode* pNode; public:     Trie()     {
           _root = new Node();         _root->_n = 0;     }     void Insert(const char* str)     {
           pNode cur = _root;         int len = strlen(str);         for (int i = 0; i < len; ++i){
               int id = str[i] - 'a';             if (cur->next[id] == NULL){
                   pNode n = new Node();                 cur->next[id] = n;                 cur = n;             }             else{
                   cur->next[id]->_n++;                 cur = cur->next[id];             }         }     }     int Search(const char* str)     {
           int len = strlen(str);         pNode cur = _root;         for (int i = 0; i < len; ++i){
               int id = str[i] - 'a';             if (cur->next[id] == NULL){
                   return 0;             }             else{
                   cur = cur->next[id];             }         }         return cur->_n;     }     void Destroy(pNode r)     {
           if (r == NULL)             return;         for (int i = 0; i < MAX; ++i)         {
               Destroy(r->next[i]);         }         delete r;     }     ~Trie()     {
           Destroy(_root);     } protected:     pNode _root; }; int main() {
       Trie t;     char a[27] = {
   0};     while(gets(a) && a[0])     {
           t.Insert(a);     }     char b[27] = {
   0};     while (scanf("%s",b) != EOF){
           printf("%d\n",t.Search(b));     }     return 0; }