【题目来源】
洛谷：P2580 于是他错误的点名开始了 - 洛谷
【题目描述】
这之后校长任命你为特派探员，每天记录他的点名。校长会提供化学竞赛学生的人数和名单，而你需要告诉校长他有没有点错名。（为什么不直接不让他玩炉石。）
【输入】
第一行一个整数 \(n\)，表示班上人数。
接下来 \(n\) 行，每行一个字符串表示其名字（互不相同，且只含小写字母，长度不超过 \(50\)）。
第 \(n+2\) 行一个整数 \(m\)，表示教练报的名字个数。
接下来 \(m\) 行，每行一个字符串表示教练报的名字（只含小写字母，且长度不超过 \(50\)）。
【输出】
对于每个教练报的名字，输出一行。
如果该名字正确且是第一次出现，输出 OK，如果该名字错误，输出 WRONG，如果该名字正确但不是第一次出现，输出 REPEAT。
【输入样例】
5
a
b
c
ad
acd
3
a
a
e
【输出样例】
OK
REPEAT
WRONG
【算法标签】
《洛谷 P2580 于是他错误的点名开始了》 #字符串# #搜索# #字典树,Trie#
【代码详解】
#include <bits/stdc++.h>
using namespace std;// 字典树节点结构体
struct node
{char c; // 当前节点存储的字符map<char, int> child; // 子节点映射（字符->索引）bool end = 0; // 标记是否为单词结尾bool repeat = 0; // 标记是否重复出现过
} root; // 字典树根节点vector<node> trie; // 字典树存储结构
int n, m; // n: 初始字符串数量, m: 查询字符串数量
string s; // 临时存储输入的字符串/*** 构建字典树* @param s 要插入的字符串*/
void build(string s)
{int fa = 0; // 当前父节点索引（从根节点0开始）node x; // 新节点临时变量for (int i = 0; i < s.size(); i++) {// 如果当前字符不存在于子节点中if (!trie[fa].child[s[i]]) {int len = trie.size(); // 获取新节点位置trie[fa].child[s[i]] = len; // 添加子节点映射x.c = s[i]; // 设置节点字符// 如果是字符串最后一个字符，标记为单词结尾if (i == s.size() - 1) {x.end = 1;}trie.push_back(x); // 添加新节点fa = len; // 移动到新节点} else {// 字符已存在，移动到对应子节点fa = trie[fa].child[s[i]];}}
}/*** 在字典树中查询字符串* @param s 要查询的字符串* @return 查询结果：0(不存在), 1(首次出现), 2(重复出现)*/
int triefind(string s)
{int fa = 0; // 从根节点开始查询for (int i = 0; i < s.size(); i++) {// 如果字符不存在于字典树中if (!trie[fa].child[s[i]]) {return 0; // 返回不存在}else {// 移动到子节点继续查询fa = trie[fa].child[s[i]];}} // 检查是否为完整单词if (trie[fa].end) {if (trie[fa].repeat) // 如果已经出现过{return 2; // 返回重复出现}else {trie[fa].repeat = 1; // 标记为已出现return 1; // 返回首次出现}} else {return 0; // 不是完整单词}
}int main()
{// 输入初始字符串数量并构建字典树cin >> n;trie.push_back(root); // 初始化字典树根节点for (int i = 0; i < n; i++) {cin >> s;build(s); // 构建字典树}// 处理查询请求cin >> m;for (int i = 0; i < m; i++) {cin >> s;int x = triefind(s); // 查询字符串// 输出查询结果if (x == 1) {cout << "OK" << endl;}else if (x == 2) {cout << "REPEAT" << endl;}else {cout << "WRONG" << endl;}}return 0;
}
【运行结果】
5
a
b
c
ad
acd
3
a
OK
a
REPEAT
e
WRONG