HDU 1247 Hat’s Words

题目链接~~>

做题感悟：开始做这道题时没想出来怎么做，后来又看了一下才想到。

解题思路：先将全部单词用字典树存起来，再依次查找所有单词看是否可行。

代码：

  

   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<string.h>
     
    
   

    

     

    
    

     

      #include<stdlib.h>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std ;
     
    
   

    

     

    
    

     

      const int MX = 1000000 ;
     
    
   

    

     

    
    

     

      char s[50005][15] ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 bool count ;
     
    
   

    

     

    
    

     
 struct node *next[26] ;
     
    
   

    

     

    
    

     

      }T[MX] ;
     
    
   

    

     

    
    

     

      int top=0 ;
     
    
   

    

     

    
    

     

      node *root ;
     
    
   

    

     

    
    

     

      node *build() // 建立节点
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     

       node *p ;
     
    
   

    

     

    
    

     

       p=&T[top++] ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<26 ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       p->next[i]=NULL ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       p->count=false ;
     
    
   

    

     

    
    

     
 return p ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      void save(char *s) // 保存单词
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int len=strlen(s) ;
     
    
   

    

     

    
    

     
 if(!len)  return ;
     
    
   

    

     

    
    

     

       node *p ;
     
    
   

    

     

    
    

     

       p=root ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<len ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int temp=s[i]-'a' ;
     
    
   

    

     

    
    

     
 if(p->next[temp]==NULL)
     
    
   

    

     

    
    

     

       p->next[temp]=build() ;
     
    
   

    

     

    
    

     

       p=p->next[temp] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       p->count=true ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      bool find(char *s)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int len=strlen(s) ;
     
    
   

    

     

    
    

     
 if(!len)  return false ;
     
    
   

    

     

    
    

     

       node *p ;
     
    
   

    

     

    
    

     

       p=root ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<len ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int temp=s[i]-'a' ;
     
    
   

    

     

    
    

     
 if(p->next[temp]==NULL)
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

       p=p->next[temp] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(p->count)
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      bool search(char *s) // 查找是否由另外两个单词组成
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 char sx[15] ;
     
    
   

    

     

    
    

     
 int len=strlen(s) ;
     
    
   

    

     

    
    

     
 if(!len)   return false ;
     
    
   

    

     

    
    

     

       node *p ;
     
    
   

    

     

    
    

     

       p = root ;
     
    
   

    

     

    
    

     
 for(int i=0 ;i<len ;i++)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int temp=s[i]-'a' ;
     
    
   

    

     

    
    

     
 if(p->next[temp]==NULL) 
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     
 else if(p->next[temp]!=NULL&&p->next[temp]->count) // 找到前一个单词，看后面剩余的单词是否存在
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 int t=0 ;
     
    
   

    

     

    
    

     
 for(int j=i+1 ;j<len ;j++)
     
    
   

    

     

    
    

     

       sx[t++]=s[j] ;
     
    
   

    

     

    
    

     

       sx[t++]='\0' ;
     
    
   

    

     

    
    

     
 if(strlen(sx)&&find(sx))
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       p=p->next[temp] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int r=0 ;
     
    
   

    

     

    
    

     

       top=0 ;
     
    
   

    

     

    
    

     

       root=build() ;
     
    
   

    

     

    
    

     
 while(~scanf("%s",s[r]))  // 不能写成 while(scanf("%s",s[r]))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       save(s[r++]) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i=0 ;i<r ;i++)
     
    
   

    

     

    
    

     
 if(search(s[i]))
     
    
   

    

     

    
    

     
 printf("%s\n",s[i]) ;
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/19234559