当前位置: 代码迷 >> PHP >> hdu 1251(字典树) 统计偏题 http://acm.hdu.edu.cn/showproblem.php?pid=1251
  详细解决方案

hdu 1251(字典树) 统计偏题 http://acm.hdu.edu.cn/showproblem.php?pid=1251

热度:590   发布时间:2012-06-30 17:20:12.0
hdu 1251(字典树) 统计难题 http://acm.hdu.edu.cn/showproblem.php?pid=1251


解题思路:直接套用字典树的模板,注意以空行结束的判断是 strcmp(str,"")==0

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
//创建一个字典树结构体
struct node{
    int num;
    struct node *br[26];
};
node *root;
//插入字母建立树
void Tree_Insert(char str[]){
    node *t , *s = root;
    int i , j;
    int len = strlen(str) - 1;
    for(i = 0 ;i <= len ; i++){
        int id = str[i] - 'a';
        if(s -> br[id] == NULL){
            t = new node;
            for(j = 0 ; j <= 25 ; j++){
                t -> br[j] = NULL;
            }
            t -> num = 0;
            s -> br[id] = t;
        }
        s = s -> br[id];
        s ->num++;
    }
}
//查找
int Tree_search(char str[]){
    node *s = root;
    int count;
    int len = strlen(str) - 1;
    for(int i = 0 ; i <= len ; i++){
        int id = str[i] - 'a';
        if(s -> br[id] == NULL){
            count = 0;
            return count;
        }
        else{
            s = s -> br[id];
            count = s -> num;
        }
    }
    return count;
}
int main(){
    int i , j;
    root = new node;
    for(i = 0 ; i <= 25 ; i++){
        root -> br[i] = NULL;
        root -> num = 0;
    }
    char str[15];
    while(gets(str),strcmp(str,"")){ //注意这里的判断条件,逗号表达式 
        Tree_Insert(str);
    }
    while(gets(str)){
        cout<<Tree_search(str)<<endl;
    }
    return 0;
}


   

  相关解决方案