字典树

模板

struct TRIE
{
    int nex[100000][26], cnt;
    bool exist[100000];  // 该结点结尾的字符串是否存在

    void insert(char* s, int l)  // 插入字符串
    {
        int p = 0;
        for (int i = 0; i < l; i++)
        {
            int c = s[i] - 'a';
            if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
            p = nex[p][c];
        }
        exist[p] = 1;
    }
    bool find(char* s, int l)  // 查找字符串
    {
        int p = 0;
        for (int i = 0; i < l; i++)
        {
            int c = s[i] - 'a';
            if (!nex[p][c]) return 0;
            p = nex[p][c];
        }
        return exist[p];
    }
};

于是他错误的点名开始了

Background

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

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

Description

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

Input

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

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

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

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

Output

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

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

Sample Input

5  
a
b
c
ad
acd
3
a
a
e

Sample Output

OK
REPEAT
WRONG

Hint

对于 40% 的数据， $n \ \leq 1000, \ m \ \leq \ 2000$
对于 70% 的数据， $n \ \leq 10^{4}, \ m \ \leq \ 2 \ \times \ 10^{4}$
对于 100% 的数据， $n \ \leq 10^{4}, \ m \ \leq \ 2 \ \times \ 10^{5}$

Solution

Trie

把模板中的标记数组 exist 改成 int，插入时标记为 1，查询时每查询一次 +1 即可判断是否 REPEAT

Accepted Code

#define _CRTSECURE_NOWARNINGS
#pragma warning(disable:4996)
#include<cstdio>
#include<cstring>
#include<string>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<iostream>
#include<queue>
#include<stack>
#include<vector>
#include<map>
#include<set>
#include<list>
using namespace std;

int n, m;
char x[101];

struct TRIE
{
    int nex[10000000][26], cnt;
    int exist[10000000];  // 该结点结尾的字符串是否存在

    void insert(char* s, int l)  // 插入字符串
    {
        int p = 0;
        for (int i = 0; i < l; i++)
        {
            int c = s[i] - 'a';
            if (!nex[p][c]) nex[p][c] = ++cnt;  // 如果没有，就添加结点
            p = nex[p][c];
        }
        exist[p] = 1;
    }
    int find(char* s, int l)  // 查找字符串
    {
        int p = 0;
        for (int i = 0; i < l; i++)
        {
            int c = s[i] - 'a';
            if (!nex[p][c]) return 0;
            p = nex[p][c];
        }
        if (exist[p]) return exist[p]++;
    }
};

TRIE trie;

int main()
{
    scanf("%d", &n);
    while (n--)
    {
        scanf("%s", x);
        int l = strlen(x);
        trie.insert(x, l);
    }
    scanf("%d", &n);
    while (n--)
    {
        scanf("%s", x);
        int l = strlen(x);
        int ans = trie.find(x, l);
        if (ans)
        {
            if (ans == 1) printf("OK\n");
            else printf("REPEAT\n");
        }
        else printf("WRONG\n");
    }

    return 0;

}