1 #include <iostream> 2 #include <string> 3 #include <typeinfo> 4 #include <vector> 5 using namespace std; 6  7 /************************************************************************/ 8 /* 树节点是两个数组，一个存储字符对应的下一节点指针 9 /* 另一个数组存储以该字符结尾的所有前缀次数*/10 /************************************************************************/11 class TreeNode12 {13 public:14     TreeNode()15     {16         for (int i=0;i<26;i++)17         {18             nextArray[i]=NULL;19             Count[i]=0;20         }21     }22     TreeNode *nextArray[26];23     int Count[26];24 };25 26 class TripTree27 {28 public:29     TripTree()30     {31         head = NULL;32     }33     void insertStr(const string &str)34     {35         if(NULL == head)36         {37             head = new TreeNode;38         }39         int i=0;40         TreeNode *temp = head;41         const int len = str.length();42         //从头到尾的构造字典树，len-1是为了防止越界43         for(;i<len-1;i++)44         {45             temp->Count[str[i]-‘a‘]++;            46             if (temp->nextArray[str[i]-‘a‘] == NULL)47             {48                 temp->nextArray[str[i]-‘a‘] = new TreeNode;49             }50             temp = temp->nextArray[str[i]-‘a‘];51                         52         }53         temp->Count[str[i]-‘a‘]++;//处理最后一个字符，因为是最后一个字符，就没有后继节点，此处不修改对应的下一个指针54     }55     int findPre(const string &str)56     {57         int i=0;58         TreeNode *temp = head;59         const int len = str.length();60         for(;i<len-1;i++)61         {62             if(temp->Count[str[i]-‘a‘] == 0||temp->nextArray[str[i]-‘a‘] == NULL)63                 return 0;64             temp = temp->nextArray[str[i]-‘a‘];65         }66         return temp->Count[str[i]-‘a‘];67     }68     TreeNode *head;69 70 };71 72 int main()73 {74     string str;75     int n;76     TripTree obj;77     while (cin >> n)78     {79         while(n--)80         {81             cin >> str;82             obj.insertStr(str);83 84         }85         cin >> n;86         while(n--)87         {88             cin >> str;89             cout << obj.findPre(str)<<endl;90 91         }92     }93     return 0;94 }