HDU--1247:Hat’s Words (字典树)

1. 题目源地址：http://acm.hdu.edu.cn/showproblem.php?pid=1247

2. 解题思路：

     第一次接触字典树，代码也是参考别人的。代码参考博客：http://blog.csdn.net/red_flame/article/details/8449537

3. 解题代码：

//HOJ--1247:Hat’s Words     字典树 
#include<iostream>
#include<string.h>
#include<string>
#define M 50005
#define N 60
using namespace std;

char str[M][N];
char s1[N],s2[N];

struct node
{
   int flag;
   node *next[26];
};

void Insert(node *root,char s[])
{
     int i=0,j,k;
     int len=strlen(s);
     node *current=root;
     
     while(i<len)
     {
        k=s[i]-'a';
        
        if(current->next[k]==NULL)
        {
           node *p=new node;
           
           for(j=0;j<26;j++)
              p->next[j]=NULL;
           p->flag=0;
              
           if(i==len-1)
              p->flag=1;
          
           current->next[k]=p;
           current=p;
        }
        
         else   current=current->next[k];
         i++;
     }
}

bool Find(node *root,char s[])
{
   int i=0,j,k;
   int len=strlen(s);
   node *current=root;
   
   while(i<len)
   {
      k=s[i]-'a';
      
      if(current->next[k]==NULL)
         return false;
         
      current=current->next[k];
      i++;
   }
   return current->flag;
}

int main()
{
    int i,j,k;
    int m,n,temp,cnt=0;
    node *root=new node;
    
    for(i=0;i<26;i++)
       root->next[i]=NULL;
    root->flag=0;
    
    while(gets(str[cnt]))
    {
       Insert(root,str[cnt]);
       cnt++;
    }
    
    for(i=0;i<cnt;i++)
    {
       temp=strlen(str[i]);
       
       for(j=1;j<temp;j++)
       {
          memset(s1,0,sizeof(s1));
          memset(s2,0,sizeof(s2));
          
          for(m=0;m<j;m++)
             s1[m]=str[i][m];
          
          for(n=j;n<temp;n++)
             s2[n-j]=str[i][n];
             
          if(Find(root,s1) && Find(root,s2))
          {
             cout<<str[i]<<endl;
             break;
          }
       }
    }
    //system("pause");
    return 0;
}