1 #include 
      
         2 #include 
       
          3  4 const int sonnum = 26;  5 char word[120005][30];  6 struct trie  7 {
     8     bool term;  9     struct trie *son[sonnum]; 10 }; 11 12 trie* create_trie() 13 {
    14     trie *temp = new trie; 15     temp -> term = false; 16     for(int i = 0;i 
        
          son[i] =NULL; 19     } 20 21     return temp; 22 } 23 24 void insert_word(trie *pnt,char s[],int len) 25 {
    26     trie *temp = pnt; 27     for(int i = 0;i 
         
           son[s[i] - 'a'] == NULL) 30             temp -> son[s[i] - 'a'] = create_trie(); 31         temp = temp -> son[s[i] - 'a']; 32     } 33     temp -> term = true; 34 } 35 36 bool find(trie *pnt ,char s[],int len) 37 {
    38     trie *temp = pnt; 39     for(int i = 0;i 
          
            son[s[i] - 'a'] == NULL) 42             return false; 43         temp = temp -> son[s[i] - 'a']; 44     } 45 46     if(temp -> term) 47     return true; 48     return false; 49 } 50 51 int main() 52 {
    53     int n = 0; 54     trie *t = create_trie(); 55     while(scanf("%s",word[n]) == 1) 56     {
    57         insert_word(t,word[n],strlen(word[n])); 58         n ++; 59     } 60 61     for(int i = 0;i < n;i ++) 62     {
    63         char s1[30],s2[30]; 64         int len = strlen(word[i]); 65         for(int j = 1;j < len ;j ++) 66         {
    67             int k; 68             for(k = 0;k < j;k ++) 69             {
    70                 s1[k] = word[i][k]; 71             } 72             s1[k] = '\0'; 73 74             for(k = j;k < len;k ++) 75             {
    76                 s2[k-j] = word[i][k]; 77             } 78             s2[k-j] = '\0'; 79             if(find(t,s1,strlen(s1))&&find(t,s2,strlen(s2))) 80             {
    81                 printf("%s\n",word[i]); 82                 break; 83             } 84         } 85     } 86     return 0; 87 }
          
         
        
       
      

知道这一题可以用hash来做，但是我不会……~~~~(>_<)~~~~