HDU 1251——Trie树

可以看博客:http://blog.csdn.net/chuck001002004/article/details/50421065了解字典树

HDU 1251：http://acm.hdu.edu.cn/showproblem.php?pid=1251

中文题不解释题意。

分析：显然这道题不是问是否有相同的单词，而是求最后一个字母在上面所有单词中出现几次，在定义Trie树节点时需要定义一个cnt，每录入一次cnt++，最后输出单词最后一个字母所对应的cnt值，若最后一个字母对应为NULL则是出0.

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
using namespace std;
char a[15];
typedef struct TrieNode
{
    int cnt;  //记录每个字母录入几次
    struct TrieNode *next[26];
}Trie;
Trie *root;
void init() //初始化函数
{
    root=(Trie*)malloc(sizeof(Trie));
    for(int i=0;i<26;i++)
        root->next[i]=NULL;
    root->cnt=0;
}
void Insert(char a[])
{
    int l=strlen(a);
    Trie *p=root;
    for(int i=0;i<l;i++)
    {
        if(p->next[a[i]-'a']==NULL) //当首次录入一个字母是
        {
            Trie *t=(Trie*)malloc(sizeof(Trie));
            for(int j=0;j<26;j++)
                t->next[j]=NULL;
            t->cnt=1;  //将cnt设为1
            p->next[a[i]-'a']=t;
            p=t;
        }
        else  //非首次录入
        {
            p=p->next[a[i]-'a'];
            p->cnt++;   //cnt自增1
        }
    }
}
int Search(char a[])
{
    int l=strlen(a);
    Trie *p=root;
    for(int i=0;i<l;i++)
    {
        if(p->next[a[i]-'a']==NULL) //当出现对应字母为空即找不到该单词时
            return 0; //返回0
        else
            p=p->next[a[i]-'a'];
    }
    return p->cnt;  //否则返回结尾字母对应的cnt值
}


int main()
{
    init();
    //本题输入单词用gets()，scanf会出问题
    while(gets(a)&&strcmp(a,"")!=0)
    {
        Insert(a);
    }
    while(gets(a)&&strcmp(a,"")!=0)
    {
        int sum=Search(a);
        printf("%d\n",sum);
    }
    return 0;
}