HDU-1251-統計難題

基本的字典樹，字典樹又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用於統計，排序和保存大量的字符串（但不僅限於字符串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：利用字符串的公共前綴來節約存儲空間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。

如上圖所示，每一個紅色節點都一個單詞，白色節點表示公共前綴

[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<cstdlib> 
using namespace std; 
struct node 
{ 
    int count; 
    node *childs[26]; 
    node() 
    { 
        count=0; 
        int i; 
        for(i=0;i<26;i++) 
        childs[i]=NULL; 
    } 
}; 
node *root=new node; 
node *current,*newnode; 
void insert(char *str) 
{ 
    int i,m; 
    current=root; 
    for(i=0;i<strlen(str);i++) 
    { 
        m=str[i]-'a'; 
        if(current->childs[m]!=NULL) 
        { 
            current=current->childs[m]; 
            ++(current->count); 
        } 
        else 
        { 
            newnode=new node; 
            ++(newnode->count); 
            current->childs[m]=newnode; 
            current=newnode; 
        } 
    } 
}  www.2cto.com
int search(char *str) 
{ 
    int i,m; 
    current=root; 
    for(i=0;i<strlen(str);i++) 
    { 
        m=str[i]-'a'; 
        if(current->childs[m]==NULL) 
        return 0; 
        current=current->childs[m]; 
    } 
    return current->count; 
} 
int main() 
{ 
    char str[20]; 
    while(gets(str),strcmp(str,"")) 
    insert(str); 
    while(gets(str)!=NULL) 
    printf("%d\n",search(str)); 
    return 0; 
}