首页 > 代码库 > [HDOJ2846]Repository（字典树）

[HDOJ2846]Repository（字典树）

2024-08-16 02:33:44   215人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2846

题意：求一堆串中有多少个以0开始的子串包含目标串。

可以把所有的串符合要求的子串放入字典树统计。这时候会有一个问题，那就是adddd这样的单词：样例中已经说明了，这样的单词明显是只算一次的。所以可以在字典树中打标记，每一个节点最后更新的时候的字符串是哪个。

 1 #include <bits/stdc++.h> 2 using namespace std; 3  4 typedef struct Node { 5     Node* next[26]; 6     int cnt, id; 7 }Node; 8 int n, q, ncnt; 9 char tmp[22];10 Node memory[350000];11 Node* rt;12 13 void insert(Node* rt, char* s, int id) {14     Node* p = rt;15     for(int i = 0; s[i]; i++) {16         int x = s[i] - ‘a‘;17         if(p->next[x] == NULL) {18             p->next[x] = &memory[ncnt++];19             p->next[x]->id = -1;20         }21         p = p->next[x];22         if(id != p->id) {23             p->cnt++;24             p->id = id;25         }26     }27 }28 29 int query(Node* rt, char* s) {30     Node* p = rt;31     for(int i = 0; s[i]; i++) {32         int x = s[i] - ‘a‘;33         if(p->next[x] == NULL) return 0;34         p = p->next[x];35     }36     return p->cnt;37 }38 39 int main() {40     // freopen("in", "r", stdin);41     while(~scanf("%d", &n)) {42         ncnt = 0;43         memset(memory, 0, sizeof(memory));44         rt = &memory[ncnt++];45         memset(rt->next, 0, sizeof(rt->next));46         for(int i = 0; i < n; i++) {47             scanf("%s", tmp);48             for(int j = 0; tmp[j]; j++) {49                 insert(rt, tmp+j, i);50             }51         }52         scanf("%d", &q);53         while(q--) {54             scanf("%s", tmp);55             printf("%d\n", query(rt, tmp));56         }57     }58     return 0;59 }

 

[HDOJ2846]Repository（字典树）


联系
我们