hdu 1247(字典树)

http://acm.hdu.edu.cn/showproblem.php?pid=1247

/*

注意结点数字的意义

刚开始还是用结点数字记录当前前缀出现的次数，结构一直出错，而找到下边例子后才发现问题。

特殊例子
a
s
d
asd
应该没有输出结果，但却输出了asd
why？
*/

题目大意：按字典序给出一些单词（不超过50000个），将那些由其它两个单词组合成的单词按字典序输出；

#include"iostream"
#include"string"
#define M 50001
#define N 50
using namespace std;
char s[M][N],s1[N],s2[N];
//结点结构
struct Node
{
	int nCount;
	Node *next[26];
}*root;
//初始化新结点
void Init(Node *p)
{
	int i;
	p->nCount=0;
	for(i=0;i<26;i++){
		p->next[i]=NULL;
	}
}
//插入新单词
void Insert(char *s)
{
	int i,k;
	Node *p=root;
	Node *newnode;
	for(i=0;i<strlen(s);i++){
		k=s[i]-'a';
		if(p->next[k]==NULL){
			newnode=new Node;
			Init(newnode);
			p->next[k]=newnode;
			p=newnode;
		}
		else{
			p=p->next[k];
		}
	}
	p->nCount=1;//标记一个单词
}
//搜索单词
int Search(char *s)
{
	int i,k;
	Node *p=root;
	for(i=0;i<strlen(s);i++){
		k=s[i]-'a';
		if(p->next[k]==NULL)
			return 0;
		else
			p=p->next[k];
	}
	return p->nCount;
}
//释放内存
void Freedom(Node *p)
{
	for(int i=0;i<26;i++){
		if(p->next[i]!=NULL){
			Freedom(p->next[i]);
		}
	}
	delete p;
}
int main()
{
	int i,j,k,l;
	root=new Node;
	Init(root);
	int num=0;
	while(gets(s[num])){
		Insert(s[num]);
		num++;
	}
	for(i=0;i<num;i++){
		for(j=1;j<strlen(s[i]);j++){   //把单词从各个位置分成两个单词 s1,s2，判断是否同时出现过
			for(k=0;k<j;k++)
				s1[k]=s[i][k];
			s1[k]='\0';
			for(k=0,l=j;l<strlen(s[i]);k++,l++)
				s2[k]=s[i][l];
			s2[k]='\0';
			if(Search(s1)&&Search(s2)){
				cout<<s[i]<<endl;
				break;
			}
		}
	}
	return 0;
}