题目链接在这里:P2580 于是他错误的点名开始了 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
是一道trie树的板子题,注意理解trie树的每一个节点代表的是一个状态,这个状态是一个前缀。
1 #include "bits/stdc++.h"
2 using namespace std;
3 const int MAX=5e5+5;
4 int n,m;
5 struct Str{
6 int str[MAX][30],tot;
7 int cnt[MAX];
8 bool vis[MAX];
9 Str(){
10 tot=0;
11 memset(vis,false,sizeof(vis));
12 memset(str,0,sizeof(str));
13 memset(cnt,0,sizeof(cnt));
14 }
15 void insert(char *s){
16 int i,j,p=0;
17 int ls=strlen(s+1);
18 for (i=1;i<=ls;i++){
19 if (str[p][s[i]-'a']==0){
20 str[p][s[i]-'a']=++tot;
21 p=tot;
22 }
23 else p=str[p][s[i]-'a'];
24 }
25 vis[p]=true;
26 }
27 int check(char *s){
28 int i,j,ls,p=0;
29 ls=strlen(s+1);
30 for (i=1;i<=ls;i++){
31 if (str[p][s[i]-'a']==0) return 0;
32 p=str[p][s[i]-'a'];
33 }
34 if (!vis[p]) return 0;
35 if (cnt[p]==0){
36 cnt[p]++;
37 return 1;
38 }
39 else return 2;
40 }
41 }ss;
42 int main(){
43 int i,j;char s[MAX];
44 scanf("%d",&n);
45 for (i=1;i<=n;i++){
46 scanf("\n%s",s+1);
47 ss.insert(s);
48 }
49 scanf("%d",&m);
50 for (i=1;i<=m;i++){
51 scanf("\n%s",s+1);
52 j=ss.check(s);
53 if (j==0) printf("WRONG\n");
54 if (j==1) printf("OK\n");
55 if (j==2) printf("REPEAT\n");
56 }
57 return 0;
58 }
标签:cnt,点名,vis,Trie,MAX,int,str,字符串,return From: https://blog.51cto.com/u_15793969/5871252