SDUT 1500 Message Flood trie树

题目连接：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  struct node
  5 {
  6     int flag;
  7     struct node *next[27];
  8 };
  9 struct node *new_node()
 10 {
 11     struct node *p;
 12     p = (struct node *)malloc(sizeof(struct node));
 13     int i;
 14     for(i = 0;i < 27;i++)
 15     {
 16         p->next[i] = NULL;
 17     }
 18     p->flag = 0;
 19     return p;
 20 }
 21 void insert(struct node *rt,char *s)
 22 {
 23     struct node *p;
 24     p = rt;
 25     int t,i;
 26     for(i = 0;s[i] != '\0';i++)
 27     {
 28         if(s[i] >= 'A' && s[i] <= 'Z')
 29         s[i] =s[i]-'A'+'a';
 30         t = s[i]-'a';
 31         if(p->next[t] == NULL)
 32         p->next[t] = new_node();
 33         p = p->next[t];
 34     }
 35     p->flag = 1;
 36 
 37 }
 38 
 39 int search(struct node *rt,char s[])
 40 {
 41     int i;
 42     struct node *p;
 43     p = rt;
 44     for(i = 0; s[i] != 0;i++)
 45     {
 46         if(s[i] >= 'A' && s[i] <= 'Z')
 47         s[i]+=32;
 48         int t;
 49         t = s[i]- 'a';
 50         if(p->next[t] == NULL)
 51             return 0;
 52         p = p->next[t];
 53     }
 54     if(p->flag)
 55     {
 56         p->flag = 0;
 57         return 1;
 58     }
 59     return 0;
 60 }
 61 void del(struct node * p)
 62 {
 63     int i;
 64     if(p)
 65     {
 66         for(i=0;i<26;i++)
 67             if(p->next[i])
 68                 del(p->next[i]);
 69     }
 70     free(p);
 71     p=NULL;
 72 }
 73 int main()
 74 {
 75     char s[105];
 76     int n,m,i,j,leap;
 77     while(~scanf("%d",&n)&&n)
 78     {
 79         scanf("%d",&m);
 80         struct node *rt;
 81         rt = new_node();
 82         leap = 0;
 83         int temp =  n;
 84         while(n--)
 85         {
 86             scanf("%s",s);
 87             insert(rt,s);
 88         }
 89         leap = 0;
 90         while(m--)
 91         {
 92             scanf("%s",s);
 93             if(search(rt,s))
 94             leap++;
 95 
 96         }
 97         del(rt);
 98         printf("%d\n",temp-leap);
 99     }
100     return 0;
101 }