hdu 2896 字典树解法

  1 #include <iostream>
  2 #include <cstring>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 #include <algorithm>
  6 using namespace std;
  7 struct Tree
  8 {
  9     Tree *next[94];
 10     bool isVirus;
 11     int num;
 12 };
 13 Tree *root;
 14 int all;
 15 char temp[10001];
 16 int temps[10001];
 17 int n,m;
 18 void insert(char temp[],int Num)
 19 {
 20     int len=strlen(temp);
 21     Tree *the=root;
 22     for(int i=0; i<len; i++)
 23     {
 24         int temps=temp[i]-‘ ‘;
 25         if(the->next[temps]==NULL)
 26         {
 27             Tree* ttemp=(Tree *)malloc(sizeof(Tree));
 28             for(int j=0; j<94; j++)
 29                 ttemp->next[j]=NULL;
 30             ttemp->isVirus=false;
 31             if(i==len-1)
 32             {
 33                 ttemp->isVirus=true;
 34                 ttemp->num=Num;
 35             }
 36             the->next[temps]=ttemp;
 37         }
 38         else if(i==len-1)
 39         {
 40             the->next[temps]->isVirus=true;
 41             the->next[temps]->num=Num;
 42         }
 43         the=the->next[temps];
 44     }
 45 }
 46 void search(int num)
 47 {
 48     int virusNum=0;
 49     int vir[3];
 50     int len=strlen(temp);
 51     for(int i=0; i<len; i++)
 52     {
 53         Tree* the=root;
 54         for(int j=0; i+j<len; j++)
 55         {
 56             int ttemp=(int)(temp[i+j]-‘ ‘);
 57             if(the->next[ttemp]==NULL)break;
 58             else if(the->next[ttemp]->isVirus)
 59             {
 60                 bool ok=false;
 61                 for(int s=0; s<virusNum; s++)
 62                 {
 63                     if(vir[s]==the->next[ttemp]->num)
 64                         ok=true;
 65                 }
 66                 if(!ok)
 67                 {
 68                     vir[virusNum++]=the->next[ttemp]->num;
 69                     i=i+j;
 70                     break;
 71                 }
 72                 else
 73                     the=the->next[ttemp];
 74             }
 75             else
 76                 the=the->next[ttemp];
 77         }
 78         if(virusNum==3)break;
 79     }
 80     if(virusNum)
 81     {
 82         all++;
 83         printf("web %d:",num);
 84         sort(vir,vir+virusNum);
 85         for(int i=0; i<virusNum; i++)
 86             printf(" %d",vir[i]);
 87         printf("\n");
 88     }
 89 }
 90 int main()
 91 {
 92     int virusNum;
 93     int vir[3];
 94     root=(Tree *)malloc(sizeof(Tree));
 95     for(int i=0; i<94; i++)
 96         root->next[i]=NULL;
 97     root->isVirus=false;
 98     cin>>n;
 99     for(int i=1; i<=n; i++)
100     {
101         scanf("%s",temp);
102         insert(temp,i);
103     }
104     cin>>m;
105     for(int i=1; i<=m; i++)
106     {
107         scanf("%s",temp);
108         search(i);
109     }
110     printf("total: %d\n",all);
111     return 0;
112 }