hdu 1251(简单trie)

这道题简单，1Y，开始delete（）是用的~trie中写的，0ms,但是内存很大
我以为是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;

}

posted on 2008-05-07 20:32 zoyi 阅读(409) 评论(0) 编辑收藏引用所属分类: acm 、数据结构

朋友

搜索

最新评论

1. re: 欧拉定理证明 && 欧拉公式
@我没有名字
@我没有名字
因为a * xi 与n互质，所以a * xi mod n与n互质，又因为a * xi mod n < n, 所以 a * xi mod n ∈ Zn
--煎蛋
2. re: 大素数的检验
好文章~
--vcvycy
3. re: 大素数的检验
@菜鸟

1007不是素数
--edwinkoo
4. re: 大素数的检验[未登录]
评论内容较长,点击标题查看
--菜鸟
5. re: 欧拉定理证明 && 欧拉公式
评论内容较长,点击标题查看
--我没有名字

阅读排行榜

评论排行榜

常用链接

留言簿(8)

随笔分类

随笔档案

文章档案

相册

acmer

online judge

队友

技术

朋友

搜索

最新评论

阅读排行榜

评论排行榜

只有注册用户登录后才能发表评论。


相关文章: 一个有意思的问题--从跳舞想到 pku 3111 (迭代or二分) pku 3110 贪心大素数的检验 spoj 6 Simple Arithmetics pku 2761 spoj The Next Palindrome 动态统计的静态实现（李睿） spoj Sum of one-sequence pku 2917 Diophantus of Alexandria

网站导航: 博客园 IT新闻 BlogJava 知识库博问管理