洛谷题单指南-字符串-P2580 于是他错误的点名开始了

原题链接：https://www.luogu.com.cn/problem/P2580

题意解读：给n个字符串，再依次处理m个字符串，对于每个字符串，如果在前面n个字符串中输出OK，如果不在n个字符串中输出WRONG，如果在n个字符串中且不止一次查询过输出REPEAT。

解题思路：

1、set/map

方法很简单直接，用set存下前n个字符串, map记录后m个字符串每个字符串出现次数，然后一一遍历m个字符串去set里查找，如果找到就再到map里判断查找过的次数。

100分代码：

#include <bits/stdc++.h>
using namespace std;

int n, m;
set<string> a;
map<string, int> b;

int main()
{
    cin >> n;
    string str;
    while(n--) 
    {
        cin >> str;
        a.insert(str);
    }
    cin >> m;
    while(m--)
    {
        cin >> str;
        b[str]++;
        int ac = a.count(str), bc = b[str];
        if(ac > 0 && bc > 1) cout << "REPEAT" << endl;
        else if(ac > 0) cout << "OK" << endl;
        else cout << "WRONG" << endl;
    }
    return 0;
}

2、Trie树

将n个姓名全部存入Trie树，对于后m个姓名，每个姓名都在Trie树中查找，判断是否存在，如果存在同时记录已经查找过的次数。

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 10000 * 50 + 5;
int n, m;
int son[N][26], idx, cnt[N], query[N];

void add(string str)
{
    int u = 0;
    for(int i = 0; i < str.size(); i++)
    {
        int v = str[i] - 'a';
        if(son[u][v] == 0) son[u][v] = ++idx;
        u = son[u][v];
    }
    cnt[u]++;
}

bool find(string str)
{
    int u = 0;
    for(int i = 0; i < str.size(); i++)
    {
        int v = str[i] - 'a';
        if(son[u][v] == 0) 
        {
            cout << "WRONG" << endl;
            return false;
        } 
        u = son[u][v];
    }
    if(cnt[u]) 
    {
        cout << (query[u] > 0 ? "REPEAT" : "OK") << endl;
        query[u]++;
    }   
    else cout << "WRONG" << endl;
    return true;
}

int main()
{
    cin >> n;
    string str;
    while(n--) 
    {
        cin >> str;
        add(str);
    }
    cin >> m;
    while(m--)
    {
        cin >> str;
        find(str);
    }
    return 0;
}