題目地址：http://acm.hdu.edu.cn/showproblem.php?pid=2072

題目概述：

　　給你一些句子，統計每個句子中單詞的個數。

大致思路：

　　這個題有幾種思路，一種是用Tire樹，在插入單詞過程中如果新建了一個節點便說明這個單詞是新單詞，需要注意的是有些單詞可能是另一些的前綴，這里需要特殊處理一下。

　　還有就是STL了，map，set都行，因為我沒有用STL就不細說了。

代碼：

1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cmath> 5 #include <vector> 6 #include <ctime> 7 #include <map> 8 #include <queue> 9 #include <cstring> 10 #include <algorithm> 11 using namespace std; 12 13 #define sacnf scanf 14 #define maxn 10010 15 #define inf 1061109567 16 #define Eps 0.001 17 #define PI 3.1415927 18 #define mod 9973 19 #define MAXNUM 10000 20 void Swap(int &a,int &b) {int t=a;a=b;b=t;} 21 int Abs(int x) {return (x<0)?-x:x;} 22 typedef long long ll; 23 24 struct node 25 { 26 bool End; 27 node *next[26]; 28 } tire; 29 30 bool Insert(node *root,char *s2) 31 { 32 node *p=root;int t; 33 bool ans=false; 34 while(*s2!='\0') 35 { 36 t=*s2-'a'; 37 if(p->next[t]==NULL) 38 { 39 node *temp=(node *)malloc(sizeof(node)); 40 for(int i=0;i<26;i++) temp->next[i]=NULL; 41 temp->End=false;p->next[t]=temp;ans=true; 42 } 43 p=p->next[t];s2++; 44 } 45 if(!p->End) ans=true; 46 p->End=true; 47 return ans; 48 } 49 50 void Delete(node *root) 51 { 52 for(int i=0;i<26;i++) 53 if(root->next[i]!=NULL) Delete(root->next[i]); 54 free(root); 55 } 56 57 int main() 58 { 59 //freopen("data.in","r",stdin); 60 //freopen("data.out","w",stdout); 61 //clock_t st=clock(); 62 char s2[maxn]; 63 int cnt;char s; 64 while(1) 65 { 66 node *root=(node *)malloc(sizeof(node)); 67 for(int i=0;i<26;i++) root->next[i]=NULL; 68 root->End=false;int lenb=0;cnt=0; 69 while(scanf("%c",&s)!=EOF) 70 { 71 if(s=='#') return 0; 72 if(s=='\n') break; 73 if(s<'a'||s>'z') 74 { 75 if(lenb!=0) 76 { 77 s2[lenb]='\0'; 78 if(Insert(root,s2)) cnt++; 79 lenb=0; 80 } 81 } 82 else s2[lenb++]=s; 83 } 84 if(lenb!=0) 85 { 86 s2[lenb]='\0'; 87 if(Insert(root,s2)) cnt++; 88 lenb=0; 89 } 90 printf("%d\n",cnt); 91 Delete(root); 92 } 93 //clock_t ed=clock(); 94 //printf("\n\nTime Used : %.5lf Ms.\n",(double)(ed-st)/CLOCKS_PER_SEC); 95 return 0; 96 }

?

轉載于:https://www.cnblogs.com/CtrlKismet/p/6352112.html

總結

以上是生活随笔為你收集整理的HDOJ2072解题报告【字典树】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。