Hat’s Words

 1 #include<algorithm> 2 #include<iostream> 3 #include<cstdio> 4 #include<cmath> 5 #include<cstring> 6 using namespace std; 7 struct node 8 { 9     bool k;                    //标记10     node *next[26];     //26个方向表示26个字母11     node()                    //构造函数实现结构体初始化12     {13         int i;14         for(i=0; i<26; i++)         //将26个方向初始化为NULL15             next[i] = NULL;     16         k = false;                      //终止标记标记为未出现字符串终止17     }18 };19 node *head;               //头指针20 void insert_ch(char *ch)  //插入函数，将字符串插入字典树21 {22     int i;23     node *p=head,*t;24     for(i=0; i<ch[i]; i++)25     {26         if(p->next[ch[i]-‘a‘]==NULL)  //发现未拓展的方向27         {28             t=new node;               //new函数产生新的节点29             p->next[ch[i]-‘a‘]=t;     30         }31         p = p->next[ch[i]-‘a‘];    //用p迭代向下取节点32     }33     p -> k = true;                 //标记此处有一个字符串终止34 }35 bool find_ch(char *ch)             //查找函数36 {37     int i;38     node *p=head;39     for(i=0; i<ch[i]; i++)40     {41         if(p->next[ch[i]-‘a‘]==NULL)42             return false;43         p = p -> next[ch[i]-‘a‘];44     }45     return p -> k;                  //返回终止处是否有终止标记46 }47 char s[50001][101];                 48 char a[105],b[105],x;49 int main()50 {51     int i,n=0,j;52     head = new node;                  53     while(~scanf("%s%*c",s[n]))54     {55         insert_ch(s[n]);                //保存字符串并插入字典树56         n++;57     }58     for(i=0; i<n; i++)59     {60         for(j=1; j<strlen(s[i]); j++)   //遍历所有拆分的组合61         {62             x=s[i][j];63             s[i][j]=‘\0‘;64             strcpy(a,s[i]);              65             s[i][j]=x;66             strcpy(b,s[i]+j);67             if(find_ch(a) && find_ch(b))68             {69                 printf("%s\n ",s[i]);70                 break;                   //遍历到出现字符串，退出防止出现重复71             }72         }73     }74     return 0;75 }