字典树

模板

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;

}