Hat’s Words（hdu 1247）（trie tree）

Hat’s Words（hdu 1247）

一个 “hat’s word”是一个单词可以恰好由字典中其他两个单词联接得到。给出你字典中的单词，你的工作是找出字典中所有的hat’s word。

输入：

每行为一个单词，由小写英文字母组成。所有单词按照字典顺序排列，总数不超过50,000。只有一组测试数据。

输出：

输出为所有的hat’s word，且按照字典顺序输出。

输入样例：

ahat

hat

hatword

hziee

word

输出样例：

ahat

hatword

分析：

将每个单词都插入到Trie树里，并按顺序依次判断每个单词是不是hat’s word。判断一个单词是不是hat’s word时，用暴力将这个单词分成前后两部分，判断这两部分是否都出现在Trie树里。

代码：

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

char ch[50050][100];

struct node
{
    struct node * next[26];
    bool value;
    node()
    {
        for(int i = 0; i < 26; i++)
            next[i] = NULL;
        value = false;
    }
}* root;

void insert(char s[])
{
    int k = 0;
    node *p = root;
    while(s[k] != '\0')
    {
        if( ! p->next[s[k]-'a'])
            p->next[s[k]-'a'] = new node();
        p = p->next[s[k]-'a'];
        k++;
    }
    p->value = true;
}

bool find(char s[])
{
    int k = 0;
    node *p = root;
    while(s[k] != '\0' && p->next[s[k]-'a'])
    {
        p = p->next[s[k]-'a'];
        k++;
    }
    if(s[k] == '\0' && p->value)
        return p->value;
    return false;
}

int main()
{
    int i = 0, k;
    root = new node();
    while(scanf("%s", ch[i]) != EOF)
    {
        insert(ch[i]);
        i++;
    }
    for(k = 0; k < i; k++)
    {
        int j;
        for(j = 1;j < strlen(ch[k]) - 1; j++)
        {
            char s1[100], s2[100];
            for(int jj = 0; jj < j; jj++)
                s1[jj] = ch[k][jj];
            s1[j] = '\0';
            strcpy(s2, ch[k] + j);
            if(find(s1) && find(s2))
            {
                cout << ch[k] << "\n";
                break;
            }
        }
    }
    return 0;
}

Hat’s Words（hdu 1247）（trie tree）

相关推荐