【洛谷题库】于是他错误的点名开始了-题解

题目背景

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

他会一边搓炉石一边点名以至于有一天他连续点到了某个同学两次，然后正好被路过的校长发现了然后就是一顿欧拉欧拉欧拉……。

---

题意描述

这之后校长任命你为特派探员，每天记录他的点名。

校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。（为什么不直接不让他玩炉石。）

---

输入格式

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

接下来 $n$ 行，每行一个字符串表示每个人的名字。

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

接下来 $m$ 行，每行一个字符串表示教练报的名字

---

输出格式

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

如果该名字正确且是第一次出现，输出 OK.

如果该名字错误，输出 WRONG.

如果该名字正确但不是第一次出现，输出 REPEAT。

---

Input & Output ‘s examples

Input ‘s eg

5  
a
b
c
ad
acd
3
a
a
e

Output ‘s eg

OK
REPEAT
WRONG

---

数据范围和约定

对于 $40\mathrm{\%}$ 的数据，$n\le 1000,m\le 2000$；

对于 $70\mathrm{\%}$ 的数据，$n\le 10000,m\le 20000$；

对于 $100\mathrm{\%}$ 的数据， $n\le 10000，m\le 100000$。

---

分析

Trie 树的版子题。

当然你也可以用 map 轻易水过

建立一颗以 26 个字母为子节点的 Trie 树，然后直接寻找子串出现次数即可。

其他的详见代码注释。

---

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 1000001

using namespace std;

namespace Trie{
    struct Node{
        int son[27];    //可能出现的子节点，一共从a到z共26
        int cnt;        //cnt 有多少个以当前节点结尾的字符串
        int size;       //size 有多少个字符串以当前节点为前缀
        int number;     //点名的次数
    }node[N];

    int tot;

    void insert(string s){      //向Trie树中插入一个字符串
        int len = s.length() , rt = 0;
        for(int i = 0; i < len; i ++){
            int c = s[i] - 'a';     
            if(!node[rt].son[c]){
                node[rt].son[c] = ++ tot;   //如果没有这个字母，就插入
            }
            rt = node[rt].son[c];   //向下转移
            node[rt].size ++;
        }
        node[rt].cnt ++;    //统计答案，以当前节点结尾的字符串 + 1
    }

    int find(string s){
        int len = s.length() , rt = 0;
        for(int i = 0; i < len; i ++){
            int c = s[i] - 'a';
            if(!node[rt].son[c]){
                return 0;       //如果有一位找不到了，直接返回
            }
            rt = node[rt].son[c];       //向下转移
        }
        node[rt].number ++;     //被多叫到了一次
        return node[rt].number;
    }

}

using namespace Trie;

int n , m;

int main(){
    string q;
    cin >> n;
    for(int i = 1; i <= n; i ++){
        cin >> q;
        insert(q);  //把名字插入Trie树
    }
    cin >> m;
    cout << "\n";
    for(int i = 1; i <= m; i ++){
        cin >> q;
        int num = find(q);  
        if(num == 0){   //如果找不到这个名字
            cout << "WRONG" << "\n";
        }
        else if(num == 1){  //如果是第一次叫到
            cout << "OK" << "\n";
        }
        else{           //如果被叫到很多次了
            cout << "REPEAT" << "\n";
        }
    }
    return 0;
}

---

THE END