原创

转载请注明：

 

思路：先将所有的单词插入到 Trie 中，然后对于每个单词枚举前后位置

1 /*  2 PROG:   Hat’s Words  3 ID  :   yewei  4 LANG:   C++  5 */  6 #include 
     
        7 #include 
      
         8 #include 
       
          9 #include 
        
          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
         
          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
          
           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