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

传送门

题目背景

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

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

题目描述

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

输入格式

第一行一个整数 nn，表示班上人数。

接下来 nn 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 5050）。

第 n+2n+2 行一个整数 mm，表示教练报的名字个数。

接下来 mm 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 5050）。

输出格式

对于每个教练报的名字，输出一行。

如果该名字正确且是第一次出现，输出 OK，如果该名字错误，输出 WRONG，如果该名字正确但不是第一次出现，输出 REPEAT。

输入输出样例

输入 #1复制
5
a
b
c
ad
acd
3
a
a
e
输出 #1复制
OK
REPEAT
WRONG

说明/提示

对于 40%40% 的数据，n\le 1000n≤1000，m\le 2000m≤2000。
对于 70%70% 的数据，n\le 10^4n≤10
4
，m\le 2\times 10^4m≤2×10
4
。
对于 100%100% 的数据，n\le 10^4n≤10
4
，m≤10^5m≤10
5
。
\text{upd 2022.7.30}upd 2022.7.30：新增加一组 Hack 数据。

上代码:

#include <algorithm>
#include <cctype>
#include <cstdio>
#include <cstring>
#include <cmath>
#define re register
struct Trie{
    
    bool count; int next[26]; bool exist; //exist表示此处是否为一个单词；count表示此单词是否已被查询。
}a[500100]; int top(1);
char str[60]; int n, m;
char buf[10000], *p = buf, *end = buf; int lent; //不要在意读入优化，使用scanf("%d") 与 scanf("%s") 对应相应读入即可。
inline char getChar() {
    
    if(p == end) {
    
        if(feof(stdin)) return '\0';
        p = buf, end = buf + fread(buf, 1, 10000, stdin);
    }
    return *(p++);
}
inline void getString(char* str) {
    
    lent = 0; char _c;
    while (!isalpha(_c = getChar()));
    do str[lent++] = _c;
    while (isalpha(_c = getChar()));
    str[lent] = '\0';
    return ;
}
inline void getNum(int& x) {
    
    x = 0; char c;
    while(!isdigit(c = getChar()));
    do x = x * 10 + (c - '0');
    while(isdigit(c = getChar()));
    return ;
}
inline void Trie_insert() {
    //普通insert操作，将字符串一一加入字典中
    int num(0), root = 1;
    for (re int i = 0; str[i]; ++i) {
    
        num = str[i] - 'a';
        if(!a[root].next[num]) a[root].next[num] = ++top;
        root = a[root].next[num];
    }
    a[root].exist = true;
    return ;
}
inline int Trie_search() {
    //普通search操作，查询是否存在该字符串
    int num(0), root = 1;
    for (re int i = 0; str[i]; ++i) {
    
        num = str[i] - 'a';
        if(!a[root].next[num]) return 0;  //若无法查询到后继的字母，直接退出
        root = a[root].next[num];
    }
    if(!a[root].exist) return 0;  //若此处不存在字符串，返回“WRONG”
    else if(a[root].count) return 2;  //若此处字符串已被查询，返回“REPEAT”
    a[root].count = true;  //若以上均不满足，说明合法
    return 1;  //此字符串标记为已查询，返回“OK”
}
int main() {
    
    getNum(n);
    for (re int i = 1; i <= n; ++i) {
      //插入
        memset(str, 0, sizeof str);
        getString(str);
        Trie_insert();
    }
    getNum(m);
    scanf("%d", &m);
    for (re int i = 1; i <= m; ++i) {
      //查询
        memset(str, 0, sizeof str);
        getString(str);
        int tmp = Trie_search();
        if(tmp == 0) printf("WRONG\n");  //分类讨论
        else if(tmp == 1) printf("OK\n");
        else if(tmp == 2) printf("REPEAT\n");
    }
    return 0;
}