P2580 于是他错误的点名开始了

浅谈Trie树

（先放知识类qwq）

（窝是这个学姐的小迷妹qwq!!!!!

我就看着这篇blog学习了一下思想又看着《进阶指南》学习了一下代码qwq

对每一个搜过的单词（并且这个单词合法），便标记为已经访问过，输出ok，若以后再次访问该点，则输出repeat，

如果直接没有这个单词，输出wrong

然后就A了（毕竟只是一道水题）

//trie[i][j]=k，表示编号为i的节点的第j个孩子是编号为k的节点

代码qwq

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 using namespace std;
 5 const int sz = 500050;
 6 char s[55];
 7 int trie[sz][30], tot = 1, n, m;
 8 bool vis[sz];
 9 void insert(char* str) {
10     int len = strlen(str), i = 1;
11     for(int j = 0; j < len; j++) {
12         int x = str[j] - 'a';
13         if(!trie[i][x]) trie[i][x] = ++tot;
14         i = trie[i][x];
15     }
16 }
17 int search(char* str) {
18     int len = strlen(str), i = 1;
19     for(int j = 0; j < len; j++) {
20         int x = str[j] - 'a';
21         i = trie[i][x];
22         if(i == 0) return 0;
23     }
24     if(vis[i]) return 1;
25     else {
26         vis[i] = 1;
27         return 2;
28     }
29 }
30 int main() {
31     scanf("%d", &n);
32     while(n--) {
33         scanf("%s", s);
34         insert(s);
35     }
36     scanf("%d", &m);
37     while(m--) {
38         scanf("%s", s);
39         int mid = search(s);
40         if(mid == 0) printf("WRONG\n");
41         else if(mid == 2) printf("OK\n");
42         else if(mid == 1) printf("REPEAT\n");
43     }
44     return 0;
45 }

10/16 修锅，这个题数据水到，我打的根本都是错的啊它居然A了QAQ root = 1， tot = 0啊！！！！！！不对！！！！

root == tot （初始！）

//亲测luogu数据root初始为0比1块200ms

【trie树】于是他错误的点名开始了

P2580 于是他错误的点名开始了

浅谈Trie树

推荐阅读