首页 > 代码库 > 统计难题(HDU1251)

统计难题(HDU1251)

2024-07-15 14:58:46   218人阅读

Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana
band
bee
absolute
acm

ba
b
band
abc
Sample Output
2
3
1
0

题目大意：老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量。
解题思路：利用字典树，将给出的单词存起来，然后进行查找。。。。。直接套用字典树模板。。。
题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1251

 

 1 #include <stdio.h> 2 #include <string.h> 3 #include <stdlib.h> 4 #include <malloc.h> 5 #define MAX 26                  /* 26个字母 */ 6 typedef struct node 7 { 8     struct node *child[MAX];    /* 存储下一个字符 */ 9     int n;                      /* 记录当前单词出现的次数 */10 }node, *Node;11 Node root;                      /* 字典树的根结点(不存储任何字符) */12 void insert(char *str)          /* 插入单词 */13 {14     int i, index, len;15     Node t = NULL, newnode = NULL;16     len = strlen(str);17     t = root;                   /* 开始时当前的结点为根结点 */18     for (i = 0; i < len; i++)   /* 逐个字符插入 */19     {20         index = str[i] - ‘a‘;   /* 获取此字符的下标 */21         if (t->child[index] != NULL) /* 字符已在字典树中 */22         {23             t = t->child[index];     /* 修改当前的结点位置 */24             (t->n)++;                /* 当前单词又出现一次, 累加 */25         }26         else                         /* 此字符还没出现过, 则新增结点 */27         {28             newnode = (Node)calloc(1, sizeof(node)); /* 新增一结点, 并初始化 */29             t->child[index] = newnode;30             t = newnode;            /* 修改当前的结点的位置 */31             t->n = 1;               /* 此新单词出现一次 */32         }33     }34 }35 int find_word(char *str)/* 在字典树中查找单词 */36 {37     int i, index, len;38     Node t = NULL;39     len = strlen(str);40     t = root;                       /* 查找从根结点开始 */41     for (i = 0; i < len; i++)42     {43         index = str[i] - ‘a‘;       /* 获取此字符的下标 */44         if (t->child[index] != NULL) /* 当前字符存在字典树中 */45             t = t->child[index];    /* 修改当前结点的位置 */46         else47             return 0;               /* 还没比较完就出现不匹配, 字典树中没有此单词 */48     }49     return t->n;                    /* 此单词出现的次数 */50 }51 void Dele(Node root)                /*释放内存*/52 {53     int i;54     if (NULL == root)55         return;56 57     for (i = 0; i < MAX; i++)58         if ( root->child[i] != NULL )59             Dele( root->child[i] );60     free( root );61     root = NULL;62 }63 int main()64 {65     char tmp[11];66     root = (Node)calloc(1, sizeof(node));67     while (gets(tmp)&& strlen(tmp))68         insert( tmp );69     while (scanf("%s", tmp) != EOF)70         printf("%d\n", find_word( tmp ));71     Dele( root );72     return 0;73 }
代码

 

 

 

 

 

 


联系
我们