Hat’s Words hdu1247 字典树+搜寻

Hat’s Words hdu1247 字典树+搜索

   先把单词用字典树存储，再依次对每个单词枚举拆分点，看拆分后的两个单词是否都有。

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node
{
	bool isTail;
	node *next[26];
}memory[1000000],*root;
int cur;
char word[50005][15];

node *build_node()
{
	node *p=&memory[cur++];
	for(int i=0;i<26;i++)
		p->next[i]=NULL;
	p->isTail=false;
	return p;
}

void insert_tree(char *s)
{
	int len=strlen(s);
	node *p=root;
	for(int i=0;i<len;i++)
	{
		if(p->next[s[i]-'a']==NULL)
			p->next[s[i]-'a']=build_node();
		p=p->next[s[i]-'a'];
	}
	p->isTail=true;
}

bool query(char *s,int len,int cnt)//cnt起标记作用，记录是否已分成两个单词
{
	node *p=root;
	for(int i=0;i<len;i++)
	{
		p=p->next[s[i]-'a'];
		if(p==NULL)
			return false;
		if(cnt==1&&p->isTail)
			if(i<len-1&&query(&s[i+1],len-i-1,2))
				return true;
	}
	if(cnt==2&&p->isTail)
		return true;
	return false;
}

int main()
{
	int i=0;
	cur=0;
	root=build_node();
	while(~scanf("%s",word[i]))
		insert_tree(word[i++]);
	for(int j=0;j<i;j++)
		if(query(word[j],strlen(word[j]),1))
			printf("%s\n",word[j]);
	return 0;
}