我以為是trie中的空間沒釋放掉,所以改用了遞歸刪除,結果500ms,差距阿,以后要注意了
寫這道題主要是復習一下,以下是代碼,比以前寫的簡化了很多
#include<iostream>
#include<algorithm>
#define MaxN 26
const char stdt='a';
using namespace std;
struct trie
{
trie* next[MaxN];
int val;
trie()
{
int i;
for(i=0;i<MaxN;i++)next[i]=0;
val=0;
}
~trie()
{
int i;
for(i=0;i<MaxN;i++)delete(next[i]);
}
};
int main()
{
char words[12],*t;
int ans;
trie* root=new trie,*p;
while(gets(words)&&strcmp(words,"")){
p=root;
t=words;
while(*t){
if(p->next[*t-stdt]==0)
p->next[*t-stdt]=new trie;
p=p->next[*t-stdt];
(p->val)++;
t++;
}
}
while(scanf("%s",words)!=EOF){
p=root;
t=words;
while(*t){
if(p->next[*t-stdt]==0){
ans=0; break;}
p=p->next[*t-stdt];
ans=p->val;
t++;
}
printf("%d\n",ans);
}
return 0;
}

