SDUT 1500 Message Flood
12847 ワード
辞書ツリーテンプレートの問題.
タイトルリンクhttp://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1500
View Code
タイトルリンクhttp://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=1500
View Code
1 #include<stdio.h>
2 #include<string.h>
3 #include<stdlib.h>
4 #define N 26
5 struct node
6 {
7 int num;
8 struct node *next[N];
9 }tree[21000];
10 int t=0;
11 struct node *creat()
12 {
13 int i;
14 struct node *p;
15 //p=&tree[t++]; 。 RE。 ？
16 p=(struct node*)malloc(sizeof(struct node));
17 for(i=0;i<N;i++)
18 p->next[i]=NULL;
19 p->num=0;
20 return p;
21 }
22 void Insert(struct node *root,char *s)
23 {
24 int i,len,ans;
25 len=strlen(s);
26 struct node *p=root;
27 for(i=0;i<len;i++)
28 {
29 if(s[i]>='A' && s[i]<='Z') ans=s[i]-'A';
30 else ans=s[i]-'a';
31 if(p->next[ans]==NULL) p->next[ans]=creat();
32 p=p->next[ans];
33 }
34 p->num=1;
35 }
36 int search(struct node *root,char *s)
37 {
38 struct node *p=root;
39 int i,len,ans;
40 len=strlen(s);
41 for(i=0;i<len;i++)
42 {
43 if(s[i]>='A' && s[i]<='Z') ans=s[i]-'A';
44 else ans=s[i]-'a';
45 if(p->next[ans]==NULL) return 0;
46 p=p->next[ans];
47 }
48 if(p->num==1) {p->num=0;return 1;}
49 return 0;
50 }
51 void Delete(struct node *p)
52 {
53 int i;
54 for(i=0;i<N;i++)
55 if(p->next[i]!=NULL) Delete(p->next[i]);
56 delete p;
57 p=NULL;
58 }
59 int main()
60 {
61 int i,n,m,count;
62 char str[12];
63 struct node *p;
64 while(scanf("%d",&n)!=EOF && n)
65 {
66 scanf("%d",&m);
67 p=creat();
68 for(i=0;i<n;i++)
69 {
70 scanf("%s",str);
71 Insert(p,str);
72 }
73 count=0;
74 while(m--)
75 {
76 scanf("%s",str);
77 count+=search(p,str);
78 }
79 printf("%d
",n-count);
80 Delete(p);
81 }
82 return 0;
83 }