#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> using namespace std; #define N 3010 struct Tire { int num; Tire *next[26]; }; Tire *root; void init() //初始化 { root = new Tire; for(int i = 0; i < 26; ++i) { root->next[i] = NULL; } } void insert(string word) { int temp, len; Tire *cur; len = word.length(); cur = root; for(int i = 0; i < len; ++i) { temp = word[i] - 'a'; if(cur->next[temp] == NULL)//不存在则创建新的节点 { Tire *newTire = new Tire; newTire->num=1; for(int j = 0; j < 26; ++j) { newTire->next[j]=NULL; } cur->next[temp]=newTire;//将新节点接到当前节点的next上 } else { cur->next[temp]->num++;//注意这个地方,num++的位置,是下一个节点的num++ } cur = cur->next[temp]; } } /*我第一次错误的写法内存没有释放完全需要递归的释放而这种释放只释放了26次 void del(Tire *root) //动态建树,用完释放内存 { for(int i = 0; i < 26; ++i) if(root->next[i] != NULL) delete(root->next[i]); }*/ void del(Tire *root) //动态建树,用完释放内存 { for(int i=0;i<10;++i) { if(root->next[i]!=NULL) del(root->next[i]); } delete(root); }//正确的写法 int search(string word) { int len, temp; Tire *cur; len = word.length(); cur = root; for(int i = 0; i < len; ++i) { temp = word[i] - 'a'; if(cur->next[temp] == NULL) return 0; cur = cur->next[temp]; } return cur->num; } int main() { init(); char word[11],ask[11]; while(gets(word)) { if(word[0]=='\0') break; insert(word); } while(gets(ask)) { int count=search(ask); printf("%d\n",count); } del(root); //释放内存 return 0; }