H - Hat’s Words HDU - 1247

  1 #include <string.h>
  2 #include <iostream>
  3 #include<cstdlib>
  4 #define MAX 26
  5 using namespace std;
  6 
  7 typedef struct TrieNode
  8 {
  9     bool isStr;
 10     struct TrieNode *next[MAX];
 11 }Trie;
 12 
 13 void insert(Trie *root,const char *s)
 14 {
 15     if(root==NULL||*s==‘\0‘)
 16         return;
 17     int i;
 18     Trie *p=root;
 19     while(*s!=‘\0‘)
 20     {
 21         if(p->next[*s-‘a‘]==NULL)
 22         {
 23             Trie *temp=(Trie *)malloc(sizeof(Trie));
 24             for(i=0;i<MAX;i++)
 25             {
 26                 temp->next[i]=NULL;
 27             }
 28             temp->isStr=false;
 29             p->next[*s-‘a‘]=temp;
 30             p=p->next[*s-‘a‘];
 31         }
 32         else
 33         {
 34             p=p->next[*s-‘a‘];
 35         }
 36         s++;
 37     }
 38     p->isStr=true;
 39 }
 40 
 41 int search(Trie *root,const char *s)
 42 {
 43     Trie *p=root;
 44     while(p!=NULL&&*s!=‘\0‘)
 45     {
 46         p=p->next[*s-‘a‘];
 47         s++;
 48     }
 49     return (p!=NULL&&p->isStr==true);
 50 }
 51 
 52 void del(Trie *root)
 53 {
 54     int i;
 55     for(i=0;i<MAX;i++)
 56     {
 57         if(root->next[i]!=NULL)
 58         {
 59             del(root->next[i]);
 60         }
 61     }
 62     free(root);
 63 }
 64 
 65 char s[50005][100];
 66 
 67 int main(int argc, char *argv[])
 68 {
 69 
 70     Trie *root= (Trie *)malloc(sizeof(Trie));
 71     for(int i=0;i<MAX;i++)
 72     {
 73         root->next[i]=NULL;
 74     }
 75     root->isStr=false;
 76 
 77     int sti = 0;
 78     while (cin>>s[sti++])
 79     {
 80         insert(root, s[sti-1]);
 81     }
 82 
 83     for(int i = 0;i < sti;i++)
 84     {
 85         char temp1[100],temp2[100];
 86         int len = strlen(s[i]);
 87         if(len !=1)
 88         {
 89             for(int tt = 1;tt <len;tt++)
 90             {
 91                 for(int j = 0;j <= tt;j++)
 92                 {
 93                     if(j!=tt)
 94                     temp1[j] = s[i][j];
 95                     if(j==tt)
 96                     temp1[j] =‘\0‘;
 97                 }
 98                 for(int j = tt,j1=0;j <=len;j++)
 99                 {
100                     if(j!=len)
101                     temp2[j1++] = s[i][j];
102                     if(j==len)
103                     temp2[j1++] = ‘\0‘;
104                 }
105 
106                 if(search(root,temp1)&&search(root,temp2))
107                    {
108                        for(int i0 = 0;i0 <len;i0++)
109                         cout<<s[i][i0];
110                         cout<<endl;
111                         break;
112                    }
113 
114             }
115         }
116 
117     }
118 
119     del(root);
120     return 0;
121 }