/*
第一次做字典樹，找了一道比較簡單的。
建樹的時候用到了new動態分配內存，剛好學C++的時候老師講到了這一點，動態內存有申請就要有釋放。
但是在網上看了好多代碼都沒有清理內存。雖然能通過題目測試，但是卻反映了一個編程態度的問題。
在此告誡自己，也希望大家都能端正自己的態度，不要為了AC而AC
*/
[cpp]
#include"iostream"
#include"cstring"
#include"cstdlib"
using namespace std;
//結點結構
struct Node
{
int ncount;
Node* Next[26];
};
Node* root;
//初始化結點
void Init(Node* t)
{
memset(t->Next,NULL,sizeof(t->Next));
t->ncount=0;
}
//插入新單詞
void Insert(char* s)
{
int i,k;
Node* p=root;
Node* newnode;
for(i=0;i<strlen(s);i++){
k=s[i]-'a';
if(p->Next[k]==NULL){
newnode=new Node;
Init(newnode);
p->Next[k]=newnode;
p=newnode;
p->ncount++;
}
else{
p=p->Next[k];
p->ncount++;
}
}
}
//搜索單詞
int Search(char* s)
{
int i,k;
Node* p=root;
for(i=0;i<strlen(s);i++){
k=s[i]-'a';
if(p->Next[k]==NULL)
return 0;
else
p=p->Next[k];
}
return p->ncount;
}
//釋放內存
void Freedom(Node* p)
{
int i;
for(i=0;i<26;i++){
if(p->Next[i]!=NULL)
Freedom(p->Next[i]);
}
delete p;
}
int main()
{
char s[11];
root=new Node;
Init(root);
while(gets(s),s[0]!='\0'){
Insert(s);
}
while(gets(s)){
int ans=Search(s);
cout<<ans<<endl;
}
Freedom(root);
return 0;
}
#include"iostream"
#include"cstring"
#include"cstdlib"
using namespace std;
//結點結構
struct Node
{
int ncount;
Node* Next[26];
};
Node* root;
//初始化結點
void Init(Node* t)
{
memset(t->Next,NULL,sizeof(t->Next));
t->ncount=0;
}
//插入新單詞
void Insert(char* s)
{
int i,k;
Node* p=root;
Node* newnode;
for(i=0;i<strlen(s);i++){
k=s[i]-'a';
if(p->Next[k]==NULL){
newnode=new Node;
Init(newnode);
p->Next[k]=newnode;
p=newnode;
p->ncount++;
}
else{
p=p->Next[k];
p->ncount++;
}
}
}
//搜索單詞
int Search(char* s)
{
int i,k;
Node* p=root;
for(i=0;i<strlen(s);i++){
k=s[i]-'a';
if(p->Next[k]==NULL)
return 0;
else
p=p->Next[k];
}
return p->ncount;
}
//釋放內存
void Freedom(Node* p)
{
int i;
for(i=0;i<26;i++){
if(p->Next[i]!=NULL)
Freedom(p->Next[i]);
}
delete p;
}
int main()
{
char s[11];
root=new Node;
Init(root);
while(gets(s),s[0]!='\0'){
Insert(s);
}
while(gets(s)){
int ans=Search(s);
cout<<ans<<endl;
}
Freedom(root);
return 0;
}
