HDOJ 1247 Hat Words Trie

原创
转载请注明：www.cnblogs.com/yewei
思路：先将所有的单词插入到 Trie 中，然后对于每个单词枚举前后位置
  1 /*
  2 PROG:   Hat’s Words
  3 ID  :   yewei
  4 LANG:   C++
  5 */
  6 #include <cstdio>
  7 #include <cstdlib>
  8 #include <cstring>
  9 #include <memory.h>
 10 
 11 //const int size = 102;
 12 const int maxn = 50004;
 13 
 14 struct Trie_Node
 15 {
 16     bool IsEnd;
 17     Trie_Node *branch[27];
 18     Trie_Node():IsEnd( false )
 19     {
 20         memset( branch, 0, sizeof(branch) );
 21     }// Init
 22 };
 23 
 24 class Trie
 25 {
 26     public:
 27         Trie();
 28         void Trie_Insert( char ss[] );
 29         bool Trie_Find( char ss[] );
 30     
 31     private:
 32         Trie_Node *root;
 33 }t;
 34 
 35 Trie::Trie()
 36 {
 37     root = new Trie_Node();
 38 }// Trie
 39 
 40 void Trie::Trie_Insert( char ss[] )
 41 {
 42     Trie_Node *ptr = root;
 43     int slen = strlen( ss );
 44     for ( int i=0; i<slen; ++i )
 45     {
 46         if ( ptr->branch[ ss[i]-'a' ]==NULL )
 47         {
 48             Trie_Node *temp = new Trie_Node();
 49             ptr->branch[ ss[i]-'a' ] = temp;
 50         }
 51         
 52         ptr = ptr->branch[ ss[i]-'a' ];
 53     }// End of for
 54     
 55     ptr->IsEnd = true;
 56     //delete temp;
 57 }// Trie_Insert
 58 
 59 bool Trie::Trie_Find( char ss[] )
 60 {
 61     Trie_Node *ptr = root;
 62     int slen = strlen( ss );
 63     for ( int i=0; i<slen; ++i )
 64     {
 65         if ( ptr->branch[ ss[i]-'a' ]!=NULL )
 66             ptr = ptr->branch[ ss[i]-'a' ];
 67         else
 68             return false;
 69     }
 70     
 71     return ptr->IsEnd;
 72 }// Trie_Find
 73 
 74 int  M=0;
 75 char words[maxn][15];
 76 
 77 void ReadData()
 78 {
 79     while ( EOF!=scanf("%s", words[M]) )
 80     {
 81         t.Trie_Insert( words[M++] );
 82     }// Insert into Trie
 83 }// ReadData
 84 
 85 void Solve()
 86 {
 87     int  tlen;
 88     char s1[15], s2[15];
 89     for ( int i=0; i<M; ++i )
 90     {
 91         tlen = strlen( words[i] );
 92         if ( tlen<2 )   continue;
 93         for ( int j=1; j<tlen; ++j )
 94         {
 95             memset( s1, 0, sizeof(s1) );
 96             memset( s2, 0, sizeof(s2) );
 97             strncpy( s1, words[i], j );
 98             strcpy( s2, words[i]+j );
 99             
100             if ( t.Trie_Find( s1 ) && t.Trie_Find( s2 ) )
101             {
102                 printf("%s\n", words[i]);
103                 break;
104             }    
105         }
106     }// End of for
107 }// Solve
108 
109 int main()
110 {
111     ReadData();
112     Solve();
113     
114     return 0;
115 }