hihoCoder#1014
剛開始學習C語言，準備在做hiho的題目的過程中來學習，在此進行記錄，如果代碼中有錯誤或者不當的地方還請指正。
描述
小Hi和小Ho是一對好朋友，出生在信息化社會的他們對編程產生了莫大的興趣，他們約定好互相幫助，在編程的學習道路上一同前進。
這一天，他們遇到了一本詞典，于是小Hi就向小Ho提出了那個經典的問題：“小Ho，你能不能對于每一個我給出的字符串，都在這個詞典里面找到以這個字符串開頭的所有單詞呢？”
身經百戰的小Ho答道：“怎么會不能呢！你每給我一個字符串，我就依次遍歷詞典里的所有單詞，檢查你給我的字符串是不是這個單詞的前綴不就是了？”
小Hi笑道：“你啊，還是太年輕了！~假設這本詞典里有10萬個單詞，我詢問你一萬次，你得要算到哪年哪月去？”
小Ho低頭算了一算，看著那一堆堆的0，頓時感覺自己這輩子都要花在上面了...
小Hi看著小Ho的囧樣，也是繼續笑道：“讓我來提高一下你的知識水平吧~你知道樹這樣一種數據結構么？”
小Ho想了想，說道：“知道~它是一種基礎的數據結構，就像這里說的一樣！”
小Hi滿意的點了點頭，說道：“那你知道我怎么樣用一棵樹來表示整個詞典么？”
小Ho搖搖頭表示自己不清楚。
“你看，我們現在得到了這樣一棵樹，那么你看，如果我給你一個字符串ap，你要怎么找到所有以ap開頭的單詞呢？”小Hi又開始考校小Ho。
“唔...一個個遍歷所有的單詞？”小Ho還是不忘自己最開始提出來的算法。
“笨！這棵樹難道就白構建了！”小Hi教訓完小Ho，繼續道：“看好了！”
“那么現在！趕緊去用代碼實現吧！”小Hi如是說道
輸入
輸入的第一行為一個正整數n，表示詞典的大小，其后n行，每一行一個單詞（不保證是英文單詞，也有可能是火星文單詞哦），單詞由不超過10個的小寫英文字母組成，可能存在相同的單詞，此時應將其視作不同的單詞。接下來的一行為一個正整數m，表示小Hi詢問的次數，其后m行，每一行一個字符串，該字符串由不超過10個的小寫英文字母組成，表示小Hi的一個詢問。
在20%的數據中n, m<=10，詞典的字母表大小<=2.
在60%的數據中n, m<=1000，詞典的字母表大小<=5.
在100%的數據中n, m<=100000，詞典的字母表大小<=26.
本題按通過的數據量排名哦～
輸出
對于小Hi的每一個詢問，輸出一個整數Ans,表示詞典中以小Hi給出的字符串為前綴的單詞的個數。
- 樣例輸入
-
5 babaab babbbaaaa abba aaaaabaa babaababb 5 babb baabaaa bab bb bbabbaab
- 樣例輸出
-
1 0 3 0 0
- 題目比較簡單，直接給出代碼
#include <stdio.h> #include <stdlib.h> typedef struct TPoint { int Num; int BranchNum; struct TPoint **next; char Symbol; }point; void insert_word(char *word,point *Current); int search_prefixion(char *word,point *Current); point *search_char(point *Current,char Ch); void free_tree(point *Rootp); int main() { int n,i; char word[10]; point Rootp={0}; scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s",word); insert_word(word,&Rootp); } scanf("%d",&n); for(i=0;i<n;i++) { scanf("%s",word); printf("%d\n",search_prefixion(word,&Rootp)); } free_tree(&Rootp); return 0; } void insert_word(char *word,point *Current) { int i; point *tmp; for(i=0;word[i]!='\0';i++) { if((tmp=search_char(Current,word[i]))!=NULL) { Current=tmp; } else { if(Current->BranchNum==0) Current->next=(point **)malloc(sizeof(point*)); else Current->next=(point **)realloc(Current->next,\ sizeof(point*)*(Current->BranchNum+1)); Current->next[Current->BranchNum]=malloc(sizeof(point)); Current=Current->next[Current->BranchNum++]; Current->Num=0; Current->BranchNum=0; Current->next=NULL; Current->Symbol=word[i]; } Current->Num++; } return; } int search_prefixion(char *word,point *Current) { int i; point *tmp; for(i=0;word[i]!='\0';i++) { if((tmp=search_char(Current,word[i]))!=NULL) Current=tmp; else return 0; } return Current->Num; } point *search_char(point *Current,char Ch) { int i; for(i=0;i<Current->BranchNum;i++) { if((Current->next[i])->Symbol==Ch) return Current->next[i]; } return NULL; } void free_tree(point *Current) { int i; if(Current->BranchNum==0) return; else { for(i=0;i<Current->BranchNum;i++) { free_tree(Current->next[i]); free(Current->next[i]); } free(Current->next); } return; }
浙公網安備 33010602011771號