首页 > 代码库 > Contacts(Tire模板题)

Contacts(Tire模板题)

2024-09-18 15:43:44   215人阅读

We‘re going to make our own Contacts application! The application must perform two types of operations:

  1. add name, where is a string denoting a contact name. This must store as a new contact in the application.

  2. find partial, where is a string denoting a partial name to search the application for. It must count the number of contacts starting with and print the count on a new line.

Given sequential add and find operations, perform each operation in order.

Input Format

The first line contains a single integer, , denoting the number of operations to perform. Each line of the subsequent lines contains an operation in one of the two forms defined above.

Constraints

  • It is guaranteed that and contain lowercase English letters only.

  • The input doesn‘t have any duplicate for the operation.

Output Format

For each find partial operation, print the number of contact names starting with on a new line.

Sample Input

4add hackadd hackerrankfind hacfind hak

Sample Output

20

Explanation

We perform the following sequence of operations:

  1. Add a contact named hack.

  2. Add a contact named hackerrank.

  3. Find and print the number of contact names beginning with hac. There are currently two contact names in the application and both of them start with hac, so we print on a new line.

  4. Find and print the number of contact names beginning with hak. There are currently two contact names in the application but neither of them start with hak, so we print on a new line.

技术分享

Code:

技术分享
  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 SFI64(x)    scanf("%I64d" , &x) 18 #define PFF(x)         printf("%f" , x) 19 #define PFD(x)         printf("%lf" , x) 20 #define PFI(x)         printf("%d" , x) 21 #define PFC(x)         printf("%c" , x) 22 #define PFS(x)         printf("%s" , x) 23 #define PFI64(x)       printf("%I64d" , x) 24 #define SPACE          printf(" ") 25 #define PUT            puts("") 26 #define LPUP(i , j , k) for(int i = j ; i <= k ; ++i) 27 #define LPDW(i , j , k) for(int i = j ; i >= k ; --i) 28 #define PB(x)          push_back(x) 29 #define ALL(A)         A.begin(), A.end() 30 #define SZ(A)          int((A).size()) 31 #define LBD(A, x)      (lower_bound(ALL(A), x) - A.begin()) 32 #define UBD(A, x)      (upper_bound(ALL(A), x) - A.begin()) 33 #define LOCAL 34 static const double PI = acos(-1.0); 35 static const double EPS = 1e-8; 36 static const int INF = 0X3fffffff; 37 typedef double DB; 38 template<class T> inline 39 void read(T &x) 40 { 41     x = 0; 42     int f = 1 ; char ch = getchar(); 43     while (ch < ‘0‘ || ch > ‘9‘) {if (ch == ‘-‘) f = -1; ch = getchar();} 44     while (ch >= ‘0‘ && ch <= ‘9‘) {x = x * 10 + ch - ‘0‘; ch = getchar();} 45     x *= f; 46     return ; 47 } 48  49 /************************Little Pea****************************/ 50  51 static const int OO = 0x3fffffff; 52 static const int MAXN = 27; 53 struct Node 54 { 55     int v; 56     Node* next[MAXN]; 57     Node() 58     { 59         v = 0; 60         CLR(next , NULL); 61     } 62 }; 63 char cmd[MAXN]; 64 char data[MAXN]; 65 Node* root; 66 void Insert(char *s , int len) 67 { 68     Node* p = root; 69     LPUP(i , 0 , len - 1) 70     { 71         int id = s[i] - ‘a‘; 72         if(p->next[id] == NULL) 73             p->next[id] = new Node(); 74         p = p->next[id]; 75         ++(p->v); 76     } 77     return ; 78 } 79 int Search(char *s , int len) 80 { 81     Node* p = root; 82     LPUP(i , 0 , len - 1) 83     { 84         int id = s[i] - ‘a‘; 85         p = p->next[id]; 86         if(!p) 87             return 0; 88     } 89     return p->v; 90 } 91 int main() 92 { 93 #ifndef ONLINE_JUDGE 94     //freopen("D:\\系统优化\\Desktop\\littlepea\\in.data" , "r" , stdin); 95 #endif 96     int n; 97     root = new Node(); 98     read(n); 99     while(n--)100     {101         SFS(cmd);SFS(data);102         if(cmd[0] == ‘a‘)103         {104             Insert(data , strlen(data));105         }106         else107         {108             PFI(Search(data , strlen(data)));109             PUT;110         }111     }112 113 #ifndef ONLINE_JUDGE114     fclose(stdin), fclose(stdout);115 #endif116 }
View Code

 

Contacts(Tire模板题)


联系
我们