SDUT 1500 Message Flood

字典树模板题。
题目链接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",n-count);
80          Delete(p);
81      }
82      return 0;
83  }