HDOJ 1247 Hat’s Words（trie树入门）

题意：

问一个字符串是否由字典里面的两个字符串组成。

思路：

字典树：建树，枚举

#include <iostream>
using namespace std;

struct node {
    bool isword;
    int child[26];
} trie[100010];

char dict[50010][21];
int size = 0;

void Insert(const char* word, int rt)
{
    if (*word == '\0')
    {
        trie[rt].isword = true;
        return ;
    }
    int m = *word - 'a';
    if (trie[rt].child[m])
    {
        Insert(word + 1, trie[rt].child[m]);
    }
    else
    {
        trie[rt].child[m] = ++size;
        Insert(word + 1, size);
    }
}

bool Query(const char* word, int rt)
{
    if (*word == '\0')
        return trie[rt].isword;

    int m = *word - 'a';
    if (!trie[rt].child[m])
        return false;
    else
        return Query(word + 1, trie[rt].child[m]);
}

int main()
{
    int n = 0;
    while (scanf("%s", dict[n]) != EOF)
        Insert(dict[n++], 0);

    char word[21];
    for (int i = 0; i < n; ++i)
    {
        bool flag = false;
        for (int j = 0; dict[i][j+1] != '\0'; ++j)
        {
            if (flag)  break;
            word[j] = dict[i][j];
            flag = Query(word, 0) && Query(&dict[i][j+1], 0);
        }
        if (flag)
            printf("%s\n", dict[i]);
        memset(word, 0, sizeof(word));
    }
    return 0;
}