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

题目背景

XS中学化学竞赛组教练是一个酷爱炉石的人。

他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次，然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉（详情请见已结束比赛CON900）。

题目描述

这之后校长任命你为特派探员，每天记录他的点名。校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。（为什么不直接不让他玩炉石。）

输入输出格式

输入格式：

第一行一个整数 n，表示班上人数。接下来 n 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 50）。第 n+2 行一个整数 m，表示教练报的名字。接下来 m 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 50）。

输出格式：

对于每个教练报的名字，输出一行。如果该名字正确且是第一次出现，输出“OK”，如果该名字错误，输出“WRONG”，如果该名字正确但不是第一次出现，输出“REPEAT”。（均不加引号）

输入输出样例

输入样例#1：

5  
a
b
c
ad
acd
3
a
a
e

输出样例#1：

OK
REPEAT
WRONG

说明

对于 40%的数据，n≤1000,m≤2000；

对于 70%的数据，n≤10000,m≤20000；

对于 100%的数据， n≤10000，m≤100000。

T1总是送分的。

code

输出注意大小写！！！

 1 #include<cstdio>
 2 #include<cstring>
 3 #define MAXN 500100
 4 
 5 struct Trie
 6 {
 7     int ch[MAXN][26];
 8     int val[MAXN];
 9     int size;
10     Trie()
11     {
12         size = 1;
13         memset(ch,0,sizeof(ch));
14         memset(val,0,sizeof(val));
15     }
16     int id(char c)
17     {
18         return c-'a';
19     }
20     void Ins(char* s)
21     {
22         int u = 0, len = strlen(s);
23         for (int i=0; i<len; ++i)
24         {
25             int c = id(s[i]);
26             if (!ch[u][c]) ch[u][c] = size++;
27             u = ch[u][c];
28         }
29         val[u] = 1;
30     }
31     int Find(char* s)
32     {
33         int u = 0, len = strlen(s);
34         for (int i=0; i<len; ++i)
35         {
36             int c = id(s[i]);
37             if (!ch[u][c]) return 0;
38             u = ch[u][c];
39         }
40         if (val[u]==1)
41         {
42             val[u] = 2;
43             return 1;
44         }
45         if (val[u]==2) return 2;
46         return 0;
47     }    
48 }t;
49 
50 int main()
51 {
52     int n,m,k;
53     char word[55];
54     scanf("%d",&n);
55     for (int i=1; i<=n; ++i)
56     {
57         scanf("%s",word);
58         t.Ins(word);
59     }
60     scanf("%d",&m);
61     for (int i=1; i<=m; ++i)
62     {
63         scanf("%s",word);
64         k = t.Find(word);
65         if (k==0) printf("WRONG
");
66         else if (k==1) printf("OK
");
67         else printf("REPEAT
"); 
68     }
69     return 0;
70 }