首页 > 代码库 > HDOJ1251-统计难题(Tire)

HDOJ1251-统计难题(Tire)

2024-09-17 16:02:12   342人阅读

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 }
View Code

 

HDOJ1251-统计难题(Tire)


联系
我们