统计难题
Time Limit: 4000/2000 MS (Java/Others) Memory Limit: 131070/65535 K (Java/Others)
Total Submission(s): 10201 Accepted Submission(s): 4156
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana band bee absolute acm ba b band abc
Sample Output
2 3 1 0
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
const int N = 26;
typedef struct Node
{
int cnt;
Node *child[26];
}Node;
Node *root;
void init()
{//对根节点初始化，根节点不存储任何数据
root =(Node *)malloc(sizeof(Node));
for(int i = 0; i < N; i++)
root->child[i] = NULL;
root->cnt = 0;
}
void insert(char *str)
{
Node *current, *newnode;
int i, j,index;
int len = strlen(str);
if(len == 0)
return;//无须插入的情况
current = root;
for(i = 0; i < len; i++)
{
index = str[i]-'a';
if(current->child[index]!=NULL)
{//子树存在
current = current->child[index];
current->cnt++;
}
else
{//子树不存在的情况
newnode =(Node *)malloc(sizeof(Node));
for(j = 0; j < N; j++)
newnode->child[j] = NULL;
newnode->cnt = 1;
current->child[index] = newnode;//这一句不可少
current = newnode; //current = current->child[index]
}
}
}
int search( char *str )
{
int i, j, k, index;
Node *current, *newnode;
current = root;
for(i=0;str[i]!= '\0';++i )
{
index=str[i]-'a';
if(current->child[index]==NULL)
return 0;
current=current->child[index];
}
return current->cnt;
}
int main()
{
char str[15];
init();
while(gets(str),strcmp(str, ""))
insert( str );
while(gets(str)!=NULL)
printf( "%d\n", search(str));
return 0;
}
//还没找到错误
#include <stdio.h>
#include <string.h>
#include <malloc.h>
#include <stdlib.h>
typedef struct Node
{
int cnt;
Node *childs[26];
Node() //不可再加上struct
{
cnt = 0;
memset(childs,NULL,sizeof(childs));
}
}Node;
Node *current, *newnode;
Node *root =(Node *)malloc(sizeof(Node));
void insert(char *str)
{
int i, j, k, index;
current=root;
for(i=0;str[i]!='\0';++i)
{
index = str[i]-'a';
if( current->childs[index]!= NULL )
{
current = current->childs[index];
++(current->cnt);
}
else
{
newnode = (Node *)malloc(sizeof(Node));
if(newnode==NULL)
exit(-1);
newnode->cnt++;//等价于 newnode->cnt=1
current->childs[index] = newnode;
current = current->childs[index];
}
}
}
int search( char *str )
{
int i, j, k, index;
current = root;
for(i=0;str[i]!= '\0';++i )
{
index=str[i]-'a';
if(current->childs[index]==NULL)
return 0;
current=current->childs[index];
}
return current->cnt;
}
int main()
{
char str[15];
while(gets(str),strcmp(str, ""))
insert( str );
while(gets(str)!=NULL)
printf( "%d\n", search(str));
return 0;
}
/*
单步调试过程中，程序产生一个访问异常（段违例）
*/
