P2580 于是他错误的点名开始了（字典树）

题目背景

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

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

题目描述

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

输入格式

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

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

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

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

输出格式

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

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

输入输出样例

输入 #1复制

5  
a
b
c
ad
acd
3
a
a
e

输出 #1复制

OK
REPEAT
WRONG

解法一

用STL map

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
int n;
int main() {
	map<string, int> student;
	string name;
	cin >> n;
	while (n--) {
		cin >> name;
		student[name] = 1;
	}
	int m; cin >> m;
	while (m--) {
		cin >> name;
		if (student[name] == 1) { puts("OK"); student[name] = 2; }
		else if (student[name] == 2) puts("REPEAT");
		else    puts("WRONG");
	}
	return 0;
}

解法二

字典树应用

1.字符串检索2.词频统计3.字典序排序4.前缀匹配

#define _CRT_SECURE_NO_WARNINGS 1
#include<bits/stdc++.h>
using namespace std;
const int N = 800000;
struct node {
	bool repeat; // 这个前缀是否重复
	int son[26]; //26个字母
	int num; // 这个前缀出现的次数
}t[N];
int cnt = 1;  // 当前新分配的存储位置把cnt = 0 留给根节点
void Insert(char* s) {
	int now = 0;
	for (int i = 0; s[i]; i++) {
		int ch = s[i] - 'a';
		if (t[now].son[ch] == 0) {
			t[now].son[ch] = cnt++;
		}
		now = t[now].son[ch];
		t[now].num++;
	}
}
int Find(char* s) {
	int now = 0;
	for (int i = 0; s[i]; i++) {
		int ch = s[i] - 'a';
		if (t[now].son[ch] == 0) return 3;
		now = t[now].son[ch];
	}
	if (t[now].num == 0) return 3; // 这个前缀没有出现过
	if (t[now].repeat == false) {
		t[now].repeat = true;
		return 1;
	}
	return 2;
}
int main() {
	char s[51];
	int n;
	cin >> n;
	while (n--) {
		scanf("%s", s);
		Insert(s);
	}
	int m;
	scanf("%d", &m);
	while (m--) {
		scanf("%s", s);
		int r = Find(s);
		if (r == 1) { puts("OK"); }
		else if (r == 2) { puts("REPEAT");}
		else { puts("WRONG"); }
	}
	return 0;
}