Hat’s Words（字典树）

短命女 2022-08-01 00:08 24阅读 0赞

# Hat’s Words #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 9455    Accepted Submission(s): 3377**

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

Author

戴帽子的

**这一题的题意是让你找到一个单词（这个单词是由本文的两个不**

**同的单词组合而成的！）**

**所以要用到[字典树][Link 1]，用其他的也写不出来啊！**

#include<cstdio>
    #include<cstring>
    #include<iostream>
    using namespace std;
    char str[50010][20];
    struct Tree
    {
        int num;//判断此节点是否为空的（就是一棵树的结束点）
        Tree *next[26];//这个是这棵树的子节点
        Tree()
        {
            num=0;
            for(int i=0;i<26;i++)
            {
                next[i]=NULL;
            }
        }//这是一棵树
    }*root;//建立一个树根
    int count1;
    void insert(Tree *p,char *s)
    {
        int i=0;
        while(s[i])//当这个字符串的某一个元素不为空的时候
        {
            int x=s[i]-'a';//看这个元素在哪里？
            if(p->next[x]==NULL)//然后看这棵树有没有这个元素如果没有
            {
                p->next[x]=new Tree();//就在这棵树的此节点重新建立一棵子树
            }
            p=p->next[x];//p指向他的子树，这一点你就可以知道了所有字符串的元素原来他们都是主仆关系没有相同的等级关系！
            i++;//继续遍历
        }
        p->num++;
    }//插入字符
    int find(Tree *p,char *s)
    {
        int i=0,ans=0;//寻找树的元素，ans是结果！
        while(s[i])//当他不为空的时候就是字符串还有的时候
        {
            int n=s[i]-'a';//找到他在这个树的节点
            if(p->next[n])//如果节点不为空
            {
                p=p->next[n];//p就指向该节点
                ans=p->num;//结果应该为1
                i++;
            }
            else
            {
                return 0;
            }
        }
        return ans;
    }
    int main()
    {
        count1=0;//用于记录单词个数的
        root=new Tree();
        while(cin>>str[count1++])
        {
            insert(root,str[count1-1]);
        }//插入1
        for(int i=0;i<count1;i++)
        {
            int len=strlen(str[i]);//得到字符串
            int flag=0;
            for(int j=0;j<len;j++)
            {
                char a[20],b[20];//进行字符串分割
                memset(a,'\0',sizeof(a));
                memset(b,'\0',sizeof(b));
                int cnt1=0;int cnt2=0;
                for(int k=0;k<j;k++)
                {
                    a[cnt1++]=str[i][k];
                }//得到a字符串
                for(int k=j;k<len;k++)
                {
                    b[cnt2++]=str[i][k];
                }//得到b字符串
                if(find(root,a)&&find(root,b))
                {
                    flag=1;//标记
                    break;
                }//查找
            }
            if(flag)
            {
                puts(str[i]);
            }
        }
    }

好东西一定要记得！

**我们一开始讲这个字典树只能寻找前缀不能寻找后缀，那么这个**

**算法到底怎么实现既能寻找前缀又能寻找后缀的呢？哦对了！他**

**是把这个字符串拆分寻找的！记住那个num他是在插入字符串后**

**的末尾记录一下，真的特别棒哦！**

[Link 1]: http://blog.csdn.net/baidu_23955875/article/details/46492093