Hat’s Words HDU - 1247 (字典树）

短命女 2023-08-17 15:41 80阅读 0赞

# Hat’s Words HDU - 1247  #

题目链接：[https://vjudge.net/problem/HDU-1247][https_vjudge.net_problem_HDU-1247]

题目：

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.

InputStandard 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.  
OutputYour 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
    题意：就是给你一个单词列表，然后单词可以从中间拆成任意两部分，只要这两部分都是单词列表里的就把这个单词输出，否则不输出
    思路：利用字典树将所有单词插入字典树中，单词个数均赋予1，然后后面处理的时候再利用strncpy函数将单词分开，分别存入s1,s2中，注意末尾要赋予“\0”
    才可使用，然后就利用字典树开始找，当find(s1)+find(s2)为2时，说明都找到了，此时将字符串输出即可；

// 
    // Created by HJYL on 2019/8/21.
    //
    #include <iostream>
    #include <vector>
    #include <map>
    #include <string>
    #include <queue>
    #include <stack>
    #include <set>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <cstdlib>
    using namespace std;
    typedef long long ll;
    const int maxn=1e6+10;
    struct trie{
        int sum;
        trie* next[26];
        trie(){
            for(int i=0;i<26;i++)
                next[i]=NULL;
            sum=0;
        }
    }root;
    void insert(char* s)
    {
        trie* p=&root;
        for(int i=0;s[i];i++)
        {
            if(p->next[s[i]-'a']==NULL)
                p->next[s[i]-'a']=new trie;
            //else
                p=p->next[s[i]-'a'];
        }
        p->sum=1;//单词存在就是1
    }
    int find(char* s)
    {
        trie* p=&root;
        for(int i=0;s[i];i++)
        {
            if(p->next[s[i]-'a']==NULL)
                return 0;
            else
                p=p->next[s[i]-'a'];
        }
        return p->sum;
    }
    int main()
    {
        //freopen("C:\\Users\\asus567767\\CLionProjects\\untitled\\text", "r", stdin);
        char str[50007][30];
        char s1[200],s2[200];
        int n=0;
        while(~scanf("%s",str[n]))
        {
            insert(str[n]);
            //cout<<str[n]<<endl;
            n++;
        }
        int len;
        int ans;
        for(int i=0;i<n;i++)
        {
            len=strlen(str[i]);
            for(int j=1;j<=len-1;j++){
                strncpy(s1,str[i],j);
                s1[j]='\0';//!
                strncpy(s2,str[i]+j,len-j);
                s2[len-j]='\0';//!
                ///cout<<s1<<" "<<s2<<endl;
                ans=find(s1)+find(s2);
                if(ans==2)
                {
                    printf("%s\n",str[i]);
                    break;
                }
            }
        }
        return 0;
    }

转载于:https://www.cnblogs.com/Vampire6/p/11386549.html

[https_vjudge.net_problem_HDU-1247]: https://vjudge.net/problem/HDU-1247