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;
}