HDU 1247 字典树 拆分单词
题目大意是要求输出所有能由其他两个单词组成的单词 题目及代码：
Hat’s Words
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6381 Accepted Submission(s): 2378
Problem Description
A hat’s word is a word in the dictionary that is the concatenation of exactly two other words in the dictionary. You are to find all the hat’s words in a dictionary.
Input
Standard input consists of a number of lowercase words, one per line, in alphabetical order. There will be no more than 50,000 words. Only one case.
Output
Your output should contain all the hat’s words, one per line, in alphabetical order.
Sample Input
a ahat hat hatword hziee word
Sample Output
ahat hatword
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 50000
struct dictree
{
dictree *child[26];
int flag;//一个标记，记录单词的结尾
}*root;
char str[MAX+10][50];
void Insert(char*source)
{
int i,j;
dictree *newnode,*current;
current=root;
for(i=0;i<strlen(source);i++)
{
if(current->child[source[i]-'a']!=0)//已经遍历过的部分
current=current->child[source[i]-'a'];
else
{
newnode=new dictree;
newnode->flag=0;
for(j=0;j<26;j++)
newnode->child[j]=0;//下一层至零便于判断结尾
current->child[source[i]-'a']=newnode;
current=current->child[source[i]-'a'];
}
}
current->flag=1;//确定叶子
}
int find(char*source)
{
dictree *current;
int i;
current=root;
for(i=0;i<strlen(source);i++)
{
if(current->child[source[i]-'a']!=0)
current=current->child[source[i]-'a'];
else
return 0;
}
return current->flag;//不错的返回值，防止遇到的是某个长字符串的子串
}
int main()
{
int i,j,k=0,l=0;
char str1[50],str2[50];
root=new dictree;//字典树的初始化操作
for(i=0;i<26;i++)//全部至零
root->child[i]=0;
root->flag=0;
while(scanf("%s",str[k])!=EOF)
{
Insert(str[k]);
k++;
}
for(i=0;i<k;i++)
{
for(j=1;j<strlen(str[i]);j++)//暴力匹配每种子串
{
strncpy(str1,str[i],j);//单词的前半部分
str1[j]=0;//很重要，不能少，用来判断结尾
strncpy(str2,str[i]+j,strlen(str[i])-j);//单词的后半部分
str2[strlen(str[i])-j]=0;//很重要，不能少，用来判断结尾
if(find(str1)&&find(str2))
{
printf("%s\n",str[i]);
break;
}
}
}
return 0;
}一条字典树的题目，初学数据结构，字典树很神奇的感觉，编了一段代码试试，感觉挺爽。。。 几点小结： 1、字典树没有线段树建树的操作，操作起来也是简单明了的，本题主要是插入、查找操作 2、数组的初始化，字典树的儿子们开始需要至零，不至零在插入时会报错 3、*重要的一点，str1[j]=0; 很重要，不能少，用来判断结尾 4、不错的返回值，防止遇到的是某个长字符串的子串 5、子串的问题刚开始考虑复杂了，由于单词长度不算长，暴力就可以了 多多总结，努力提升自己~~~