統計難題
Problem Description
Ignatius最近遇到一個難題,老師交給他很多單詞(只有小寫字母組成,不會有重復的單詞出現),現在老師要他統計出以某個字符串為前綴的單詞數量(單詞本身也是自己的前綴).
Input
輸入數據的第一部分是一張單詞表,每行一個單詞,單詞的長度不超過10,它們代表的是老師交給Ignatius統計的單詞,一個空行代表單詞表的結束.第二部分是一連串的提問,每行一個提問,每個提問都是一個字符串.
注意:本題只有一組測試數據,處理到文件結束.
Output
對於每個提問,給出以該字符串為前綴的單詞的數量.
Sample Input
banana
band
bee
absolute
acm
ba
b
band
abc
Sample Output
2
3
1
0
Author
Ignatius.L
解題思路：
這是第一次做字典樹的題目。字典樹百度百科：又稱單詞查找樹，Trie樹，是一種樹形結構，是一種哈希樹的變種。典型應用是用於統計，排序和保存大量的字符串（但不僅限於字符串），所以經常被搜索引擎系統用於文本詞頻統計。它的優點是：利用字符串的公共前綴來減少查詢時間，最大限度地減少無謂的字符串比較，查詢效率比哈希表高。
學習了字典樹之後，覺得它很明顯的就是用空間來換時間，空間復雜度特別大，比如字典數單單存26個小寫字母，那麼每個節點的孩子節點都有26個孩子節點，字典樹中的每一層都保留著不同單詞的相同字母。
為了好說明，假設，所有的單詞只包括a,b,c,d四個字母，那麼樹是這樣建立的。
題目是要求統計出以某個字符串為前綴的單詞數量，字典樹入門題。<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+tPrC66O6PC9wPgo8cD48L3A+CjxwcmUgY2xhc3M9"brush:java;">#include
#include
#include
#include
using namespace std;
char str[12];
const int maxn=26;//孩子節點的最大個數，如果是只有26個字母，就用26就可以了。
struct Trie//樹的結構體
{
int cnt;//保存某個字母出現的次數
Trie *next[maxn];//每一個節點對應著多少個孩子，如果只有26個字母，就用26就可以了
};
Trie root;
/*void init(Trie t)
{
for(int i=0;i<26;i++)
t.next[i]=NULL;
}*///不需要單獨對根節點初始化
void CreateTrie(char *str)
{
int len=strlen(str);
Trie *p=&root,*q;
for(int i=0;inext[id]==NULL)//第一次遇到
{
q=(Trie*)malloc(sizeof(Trie));
q->cnt=1;//此處一開始寫錯，寫成了q->cnt++;
for(int i=0;inext[i]=NULL;//初始化非空節點的孩子節點
p->next[id]=q;//在樹中填上
p=p->next[id];//此時的P是不為空的節點
}
else
{
p->next[id]->cnt++;//不是第一次遇到，個數++
p=p->next[id];
}
}
}
int find(char *str)
{
int len=strlen(str);
Trie *p=&root;
for(int i=0;inext[id];//一直向下走。
if(p==NULL)//找不到該單詞，一開始此處寫錯了，寫成了p->next[id]==NULL
return 0;
}
return p->cnt;
}
int main()
{
while(gets(str)&&str[0]!='\0')
{
CreateTrie(str);
}
while(scanf("%s",str)!=EOF)
{
printf("%d\n",find(str));
}
return 0;
}
