sdut 1500 Message Flood（Trie树）-白红宇

sdut 1500 Message Flood（Trie树）

阅读量：6945 次

发布时间：2019-06-27

本文共 1536 字，大约阅读时间需要 5 分钟。

题目：

View Code

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 using namespace std; 6 struct node 7 { 8     int flag; 9     node *next[26];10 };11 int num;12 node *build()13 {14     node *p;15     int i;16     p=new node;17     p->flag=0;18     for(i=0;i<26;i++)19     p->next[i]=NULL;20     return p;21 }22 void insert(node *p, char *s)23 {24     int len,i,t;25     len=strlen(s);26     for(i=0;i
          
           ='A'&&s[i]<='Z')29         t=s[i]-'A';30         else31         t=s[i]-'a';32         if(p->next[t]==NULL)33             p->next[t]=build();34         p=p->next[t];35     }36     p->flag=1;37 }38 int search(node *p,char *s)39 {40     int t,i,len;41     len=strlen(s);42     for(i=0;i
           
            ='A'&&s[i]<='Z')45 t=s[i]-'A';46 else47 t=s[i]-'a';48 if(p->next[t]==NULL)49 return 0;50 p=p->next[t];51 }52 if(p->flag==1)53 {54 num++;55 p->flag=-1;56 return 1;57 }58 return 0;59 }60 void deal(node *p)61 {62 int i;63 if(p)64 {65 for(i = 0 ;i < 26 ; i++)66 if(p->next[i])67 deal(p->next[i]);68 }69 free(p);70 p=NULL;71 }72 int main()73 {74 int m,n,i,k;75 char str[25];76 node *p;77 while(~scanf("%d",&m))78 {79 if(m==0)80 break;81 scanf("%d",&n);82 p=build();83 num=0;84 for(k=1;k<=m;k++)85 {86 scanf("%s",str);87 insert(p,str);88 }89 while(n--)90 {91 scanf("%s",str);92 search(p,str);93 }94 printf("%d\n",m-num);95 deal(p);96 }97 return 0;98 }