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

补充：软件开发 , C++ ,

上一个：hdu 1518 square
下一个：ZOJ2723 Semi_Primer