Blog·Tanky WooABOUTRSS

HDOJ 1251 统计难题

24 Sep 2010
这篇博客是从旧博客 WordPress 迁移过来,内容可能存在转换异常。

题目传送门: http://acm.hdu.edu.cn/showproblem.php?pid=1251

标准的Trie树。 题目没有什么难度,直接套模版就OK了。

资料

字典树资料: http://www.wutianqi.com/?p=1359

// Author: Tanky Woo
// www.wutianqi.com
// HDOJ 1251
// Trie
#include 
using namespace std;

typedef struct Trie{
    int v;
    Trie *next[26];
}Trie;

Trie root;

void createTrie(char *str)
{
    int len = strlen(str);
    Trie *p = &root;, *q;
    for(int i=0; inext[id] == NULL)
        {
            q = (Trie *)malloc(sizeof(root));
            q->v = 1;
            for(int j=0; j<26; ++j)
                q->next[j] = NULL;
            p->next[id] = q;
            p = p->next[id];
        }
        else
        {
            p->next[id]->v++;
            p = p->next[id];
        }
    }
}

int findTrie(char *str)
{
    int len = strlen(str);
    Trie *p = &root;
    for(int i=0; inext[id];
        if(p == NULL)
            return 0;
    }
    return p->v;
}

int main()
{
    //freopen("input.txt", "r", stdin);
    char str[15];
    int i;
    for(i=0; i<26; ++i)
        root.next[i] = NULL;
    while(gets(str) && str[0]!='\0')
        createTrie(str);
    memset(str, 0, sizeof(str));
    while(scanf("%s", str) != EOF)
    {
        int ans = findTrie(str);
        printf("%d\n", ans);
    }
    return 0;
}