今天刷了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, 0, sizeof(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 = *p - '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 = *p - '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 閱讀(138)
評論(0) 編輯 收藏 引用