首页 > 数据结构 > Hash表 > HDU 1247 Hat’s Words-字典树-[解题报告] C++
2013
12-04

HDU 1247 Hat’s Words-字典树-[解题报告] C++

Hat’s Words

问题描述 :

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.

输入:

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.

输出:

Your output should contain all the hat’s words, one per line, in alphabetical order.

样例输入:

a
ahat
hat
hatword
hziee
word

样例输出:

ahat
hatword

字典树,又称单词查找树,Trie树,是一种树形结构,典型应用是用于统计,排序和保存大量的字符串,所以经常被搜索引擎系统用于文本词频统计。它的优点是:利用字符串的公共前缀来节约存储空间,最大限度的减少无谓的字符串比较,查询效率比哈希表高。

它有三个基本性质,根节点不包含字符,除根节点外每一个节点都只包含一个字符,从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串,每个节点的所有子节点包含的字符都不相同。

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;

const int MAXN=26;
const int MAX=50005;
char word[MAX][27];

struct node
{
   bool is;
   node *next[MAXN];
   node()
   {
      is=false;
      memset(next,0,sizeof(next));
   }
};

void Insert(node *rt,char *s)
{
    int i=0;
    node *p=rt;
    while(s[i])
    {
         int k=s[i++]-'a';
         if(p->next[k]==NULL)
            p->next[k]=new node();
         p=p->next[k];
    }
    p->is=true; //该结点是单词的尾
}

bool Search(node *rt,char s[])
{
	int i=0,top=0,stack[1000];
	node *p=rt;
	while(s[i])
	{
		int k=s[i++]-'a';
		if(p->next[k]==NULL) return 0;
		p=p->next[k];
		if(p->is && s[i]) //找到该单词含有子单词的分隔点
			stack[top++]=i;//入栈
	}
	while(top)//从可能的分割点去找
	{
	    bool ok=1;
		i=stack[--top];
		p=rt;
		while(s[i])
		{
			int k=s[i++]-'a';
			if(p->next[k]==NULL)
			{
				ok=false;
				break;
			}
			p=p->next[k];
		}
		if(ok && p->is)//找到最后,并且是单词的
			return 1;
	}
	return 0;
}

int main()
{
    int i=0;
    node *rt=new node();
    while(gets(word[i]))
    {
        Insert(rt,word[i]);
        i++;
	}
	for(int j=0;j<i;j++)
		if(Search(rt,word[j]))
		   printf("%s\n",word[j]);
    return 0;
}