首页 > 代码库 > HDOJ2072-单词数(Tire树)
HDOJ2072-单词数(Tire树)
Problem Description
lily的好朋友xiaoou333最近很空，他想了一件没有什么意义的事情，就是统计一篇文章里不同单词的总数。下面你的任务是帮助xiaoou333解决这个问题。
Input
有多组数据，每组一行，每组就是一篇小文章。每篇小文章都是由小写字母和空格组成，没有标点符号，遇到#时表示输入结束。
Output
每组只输出一个整数，其单独成行，该整数代表一篇文章里不同单词的总数。
Sample Input
you are my friend
#
Sample Output
4
Solve:字典树模板题,当然也可以用set搞一搞
Code(set):
1 #include<iostream> 2 #include<string> 3 #include<sstream> 4 #include<set> 5 using namespace std; 6 int main() 7 { 8 string in; 9 set<string> all;10 while(getline(cin,in))11 {12 all.clear();13 if(in[0]==‘#‘)14 return 0;15 stringstream ss(in);16 string out;17 while(ss>>out)18 {19 all.insert(out);20 }21 cout<<all.size()<<endl;22 }23 }
Code(Tire):
1 #pragma comment(linker, "/STACK:36777216") 2 3 #include <bits/stdc++.h> 4 using namespace std; 5 #define LSON id << 1 , l , mid 6 #define RSON id << 1 | 1 , mid + 1 , r 7 #define ROOT 1 , 1 , n 8 #define CLR(x , y) memset(x , y , sizeof(x)) 9 #define LOWBIT(x) x & (-x) 10 #define FORN(i , a , n) for(int i = (a) ; i <= (n) ; ++i) 11 #define FORP(i , n , a) for(int i = (n) ; i >= (a) ; --i) 12 #define CASE(x) printf("Case %d: ", x) 13 #define SFD(x) scanf("%lf" , &x) 14 #define SFC(x) scanf(" %c" , &x) 15 #define SFS(x) scanf(" %s" , x) 16 #define SFI(x) scanf("%d" , &x) 17 #define SFL(x) scanf("%lld" , &x) 18 #define SFI64(x) scanf("%I64d" , &x) 19 #define PFF(x) printf("%f" , x) 20 #define PFD(x) printf("%lf" , x) 21 #define PFI(x) printf("%d" , x) 22 #define PFC(x) printf("%c" , x) 23 #define PFS(x) printf("%s" , x) 24 #define PFI64(x) printf("%I64d" , x) 25 #define PFL(x) printf("%lld\n" , x) 26 #define SPACE printf(" ") 27 #define PUT puts("") 28 #define LPUP(i , j , k) for(int i = j ; i <= k ; ++i) 29 #define LPDW(i , j , k) for(int i = j ; i >= k ; --i) 30 #define PB(x) push_back(x) 31 #define ALL(A) A.begin(), A.end() 32 #define SZ(A) int((A).size()) 33 #define LBD(A, x) (lower_bound(ALL(A), x) - A.begin()) 34 #define UBD(A, x) (upper_bound(ALL(A), x) - A.begin()) 35 #define LOCAL 36 static const double PI = acos(-1.0); 37 static const double EPS = 1e-8; 38 static const int INF = 0X3fffffff; 39 typedef long long LL; 40 typedef double DB; 41 template<class T> inline 42 T read(T &x) 43 { 44 x = 0; 45 int f = 1 ; char ch = getchar(); 46 while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();} 47 while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();} 48 x *= f; 49 } 50 51 /************************Little Pea****************************/ 52 53 static const int MAXN = 30; 54 int ans = 0; 55 struct Node 56 { 57 int v; 58 Node* next[MAXN]; 59 Node() 60 { 61 v = 0; 62 CLR(next , NULL); 63 } 64 }; 65 void Insert(string s , int len , Node* root) 66 { 67 Node* p = root; 68 LPUP(i , 0 , len - 1) 69 { 70 int id = s[i] - ‘a‘; 71 if(p->next[id] == NULL) 72 p->next[id] = new Node(); 73 p = p->next[id]; 74 } 75 ++(p->v); 76 } 77 int Search(Node* T) 78 { 79 if(T == NULL) 80 return 0; 81 LPUP(i , 0 , 25) 82 { 83 if(T->next[i] != NULL) 84 Search(T->next[i]); 85 } 86 if(T->v) 87 ++ans; 88 return 0; 89 } 90 91 string data; 92 int main() 93 { 94 #ifdef LOCAL 95 //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin); 96 #endif 97 while(getline(cin , data)) 98 { 99 ans = 0;100 Node* root = new Node();101 if(data[0] == ‘#‘)102 return 0;103 stringstream ss(data);104 string out;105 while(ss >> out)106 {107 int len = SZ(out);108 Insert(out , len , root);109 }110 Search(root);111 PFI(ans);PUT;112 }113 }
HDOJ2072-单词数(Tire树)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。