P2580 于是他错误的点名开始了 字典树Trie
作者:
多米尼克領主的致意
,
2024-05-14 16:09:48
,
所有人可见
,
阅读 3
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10, M = 1e5 + 10;
char name[60];
int n, m;
struct node{
bool isbend;//判结尾
int son[26];
bool repeat;
int num;
}t[8000000];
int cnt = 1;
void insert(char *s){
int now = 0;
for(int i = 0;s[i] != '\0';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++;
if(i == strlen(s) - 1)t[now].isbend = 1;
}
}
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].isbend)return 3;
if(!t[now].num)return 3;
if(!t[now].repeat){
t[now].repeat = 1;
return 1;
}
return 2;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n;
for(int i = 1;i <= n;i++){
cin >> name;
insert(name);
}
cin >> m;
for(int i = 1;i <= m;i++){
char neimu[60];
cin >> neimu;
int op = find(neimu);
if(op == 1)cout << "OK\n";
if(op == 2)cout << "REPEAT\n";
if(op == 3)cout << "WRONG\n";
}
return 0;
}