posts - 24,  comments - 0,  trackbacks - 0
今天刷了3道字典树
hdu 1251 1075  1247
摸板
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 using namespace std;
 6 typedef struct node{
 7    int cnt;
 8    struct node *b[26];
 9    void init()
10    {//printf("bsdfjihsd\n");
11        memset(b, 0sizeof(b));
12        cnt = 0;
13    }
14 }Tree;
15 Tree tree[500000];
16 int cnt = 0;
17 Tree *root = NULL;
18 void init()
19 {
20     cnt = 0;
21     root = &tree[cnt++];
22     root->init();
23 }
24 void insert(char* p)
25 {
26     node* q = root;
27     while(*p)
28     {
29         int idx = *- 'a';
30         if(0 == q->b[idx])
31         {
32             q->b[idx] = &tree[cnt++];
33             q->b[idx]->init();
34         }
35         q->b[idx]->cnt++;
36         q = q->b[idx];
37         p++;
38     }
39 }
40 
41 int query(char* p)
42 {
43     node* q = root;
44     int ans = 0;
45     while(*p)
46     {
47         int idx = *- 'a';
48         if(0 == q->b[idx])
49         {
50             ans = 0;
51             return 0;
52         }
53         ans = q->b[idx]->cnt;
54         q = q->b[idx];
55         p++;
56     }
57     return ans;
58 }
59 int main()
60 {
61     //freopen("in.txt", "r", stdin);
62     char s[20];
63     init();
64     while(gets(s))
65     {
66 
67 
68         if(strcmp(s,"\0"== 0){break;}
69         insert(s);
70     }
71     while(scanf("%s",s) != EOF)
72     {
73         int ans  = query(s);
74         printf("%d\n",ans);
75     }
76     return 0;
77 }
78 
posted on 2011-09-13 20:28 ACSeed 阅读(123) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理


<2011年9月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

常用链接

留言簿(1)

随笔档案

偶像的Blog

搜索

  •  

最新评论

阅读排行榜

评论排行榜