HDOJ 1075 What Are You Talking About（trie树入门）

思路：

字典树：建树，查询。字符串处理稍麻烦点。跑了203MS，还好

#include <iostream>
using namespace std;

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

int size = 0;

char dict[1000010][12];
char is[3010], os[3010];

void Insert(char* word, int i, int rt)
{
    if (*word == '\0')
    {
        trie[rt].isword = true;
        trie[rt].index = i;
        return ;
    }

    int m = *word - 'a';
    if (trie[rt].child[m])
    {
        Insert(word + 1, i, trie[rt].child[m]);
    }
    else
    {
        trie[rt].child[m] = ++size;
        Insert(word + 1, i, size);
    }
}

int Query(char* word, int rt)
{
    if (*word == '\0')
    {
        if (trie[rt].isword)
            return trie[rt].index;
        else
            return -1;
    }

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

int main()
{
    char mars[12];
    int i = 0;

    gets(mars);
    while (scanf("%s%*c", dict[i]))
    {
        if (!strcmp(dict[i], "END"))
            break ;
        scanf("%s%*c", mars);
        Insert(mars, i++, 0);
    }

    gets(mars);
    while (gets(is))
    {
        if (!strcmp(is, "END"))
            break;

        int i = 0, j = 0;
        memset(os, 0, sizeof(os));
        memset(mars, 0, sizeof(mars));

        for (i = 0; is[i] != '\0'; ++i)
        {
            if ('a' <= is[i] && is[i] <= 'z')
                mars[j++] = is[i];
            else
            {
                if (j)
                {
                    int m = Query(mars, 0);
                    if (m == -1)
                        strcat(os, mars);
                    else
                        strcat(os, dict[m]);
                    memset(mars, 0, sizeof(mars));
                    j = 0;
                }
                os[strlen(os)] = is[i];
            }
        }
        printf("%s\n", os);
    }
    return 0;
}