字典樹01

統計難題 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131070/65535 K (Java/Others)

hdoj: http://acm.hdu.edu.cn/showproblem.php?pid=1251

Problem Description

Ignatius最近遇到一個難題,老師交給他很多單詞(隻有小寫字母組成,不會有重複的單詞出現),現在老師要他統計出以某個字元串為字首的單詞數量(單詞本身也是自己的字首).

Input

輸入資料的第一部分是一張單詞表,每行一個單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統計的單詞,一個空行代表單詞表的結束.第二部分是一連串的提問,每行一個提問,每個提問都是一個字元串.

注意:本題隻有一組測試資料,處理到檔案結束.

Output

對于每個提問,給出以該字元串為字首的單詞的數量.

Sample Input

banana

band

bee

absolute

acm

ba

b

band

abc

Sample Output

2

3

1

正常代碼：

#include<stdio.h>
#include<string.h>
main()
{
    char str[100000][11], str2[11];
    int count, k = 0, i;
    while(gets(str[k++]) && strcmp(str[k - 1], ""));//循環儲存
    while(gets(str2) != NULL)
    {
        int count = 0;
        for( i = 0; i < k; i++)//周遊累加
            if(!strncmp(str[i], str2, strlen(str2)))
                count++;
        printf("%d\n", count);
    }
}
           

當然這個代碼是不可能AC的。。逾時是必然的，不然就不用字典樹了。

這個字典樹是我參考了别人的代碼根據自己的了解寫的，新手上路～

AC代碼：

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct Tree
{
	Tree *next[26];
	int sum;//建立一個整型變量來儲存到這個節點有多少個單詞字首相同，比如“ba”就是root -> b -> a, 在a節點就是所有字首為a的單詞的總數目
} *root;
void input(char str[])
{
	Tree *s = root;
	for(int i = 0; i < strlen(str); i++)
	{
		if(s ->next[str[i] - 'a'])//判斷下個節點是否存在
		{
			s = s -> next[str[i] - 'a'];
			s -> sum++;
		}
		else//如果下個節點不存在，建立該節點并将其初始化
		{
			Tree *t;
			t = (Tree *)malloc(sizeof(Tree));//一定不要忘了為新建立的指針申請記憶體
			memset(t, 0, sizeof(Tree));
			t -> sum = 1;
			s -> next[str[i] - 'a'] = t;
			s = t;
		}
	}
}
int find(char str[])
{
	Tree *t = root;
	for(int i = 0; i < strlen(str); i++)
	{
		if(t -> next[str[i] - 'a'])
			t = t -> next[str[i] - 'a'];
		else//如果遇到不存在的節點，說明沒有有這個字首的字元串
			return 0;
	}
	return t -> sum;
}
main()
{
	root = (Tree *) malloc(sizeof(Tree));
	memset(root, 0, sizeof(Tree));
	char str[20];
	while(gets(str) && str[0] != '\0')
		input(str);
	while(gets(str) != NULL)
		printf("%d\n", find(str));
}