首页 > 代码库 > HDOJ1251-统计难题(Tire)
HDOJ1251-统计难题(Tire)
Problem Description
Ignatius最近遇到一个难题,老师交给他很多单词(只有小写字母组成,不会有重复的单词出现),现在老师要他统计出以某个字符串为前缀的单词数量(单词本身也是自己的前缀).
Input
输入数据的第一部分是一张单词表,每行一个单词,单词的长度不超过10,它们代表的是老师交给Ignatius统计的单词,一个空行代表单词表的结束.第二部分是一连串的提问,每行一个提问,每个提问都是一个字符串.
注意:本题只有一组测试数据,处理到文件结束.
Output
对于每个提问,给出以该字符串为前缀的单词的数量.
Sample Input
banana
band
bee
absolute
acm
ba
b
band
abc
Sample Output
2
3
1
0
Solve:
Tire入门模板题,给每一个节点字母都+1,每次访问到的时候 PS:G++会MLE是什么梗
Code:
1 #pragma comment(linker, "/STACK:36777216") 2 3 #include <cstdio> 4 #include <cstring> 5 #include <cmath> 6 using namespace std; 7 #define LSON id << 1 , l , mid 8 #define RSON id << 1 | 1 , mid + 1 , r 9 #define ROOT 1 , 1 , n 10 #define CLR(x , y) memset(x , y , sizeof(x)) 11 #define LOWBIT(x) x & (-x) 12 #define FORN(i , a , n) for(int i = (a) ; i <= (n) ; ++i) 13 #define FORP(i , n , a) for(int i = (n) ; i >= (a) ; --i) 14 #define CASE(x) printf("Case %d: ", x) 15 #define SFD(x) scanf("%lf" , &x) 16 #define SFC(x) scanf(" %c" , &x) 17 #define SFS(x) scanf(" %s" , x) 18 #define SFI(x) scanf("%d" , &x) 19 #define SFL(x) scanf("%lld" , &x) 20 #define SFI64(x) scanf("%I64d" , &x) 21 #define PFF(x) printf("%f" , x) 22 #define PFD(x) printf("%lf" , x) 23 #define PFI(x) printf("%d" , x) 24 #define PFC(x) printf("%c" , x) 25 #define PFS(x) printf("%s" , x) 26 #define PFI64(x) printf("%I64d" , x) 27 #define PFL(x) printf("%lld\n" , x) 28 #define SPACE printf(" ") 29 #define PUT puts("") 30 #define LPUP(i , j , k) for(int i = j ; i <= k ; ++i) 31 #define LPDW(i , j , k) for(int i = j ; i >= k ; --i) 32 #define PB(x) push_back(x) 33 #define ALL(A) A.begin(), A.end() 34 #define SZ(A) int((A).size()) 35 #define LBD(A, x) (lower_bound(ALL(A), x) - A.begin()) 36 #define UBD(A, x) (upper_bound(ALL(A), x) - A.begin()) 37 #define LOCAL 38 static const double PI = acos(-1.0); 39 static const double EPS = 1e-8; 40 static const int INF = 0X3fffffff; 41 typedef long long LL; 42 typedef double DB; 43 template<class T> inline 44 T read(T &x) 45 { 46 x = 0; 47 int f = 1 ; char ch = getchar(); 48 while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();} 49 while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();} 50 x *= f; 51 } 52 53 /************************Little Pea****************************/ 54 55 static const int MAXN = 26; 56 char data[15]; 57 58 struct Node 59 { 60 int v; 61 Node* next[MAXN]; 62 Node() 63 { 64 v = 0; 65 CLR(next , NULL); 66 } 67 }; 68 void Insert(char *s , int len , Node* T) 69 { 70 Node* p = T; 71 LPUP(i , 0 , len - 1) 72 { 73 int id = s[i] - ‘a‘; 74 if(p->next[id] == NULL) 75 p->next[id] = new Node(); 76 ++(p->next[id]->v); 77 p = p->next[id]; 78 } 79 } 80 int Find(char *s , int len , Node* T) 81 { 82 Node* p = T; 83 LPUP(i , 0 , len - 1) 84 { 85 int id = s[i] - ‘a‘; 86 p = p->next[id]; 87 if(p == NULL) 88 return 0; 89 } 90 return p->v; 91 } 92 93 int main() 94 { 95 #ifdef LOCAL 96 //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin); 97 #endif 98 Node* root = new Node(); 99 while(gets(data) && data[0] != ‘\0‘)100 Insert(data , strlen(data) , root);101 CLR(data , ‘\0‘);102 while(~SFS(data))103 {104 PFI(Find(data , strlen(data) , root));PUT;105 }106 }
HDOJ1251-统计难题(Tire)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。