链接

https://www.luogu.org/problemnew/show/P2580

大意

给定$n$个字符串，判断$m$个字符串是否出现或没有或重复

思路

$hash$或$map$或$Trie$

由于是字典树首杀，所以随便提一提

插入

当需要插入一个字符串$S$时，我们令一个指针$p$起初指向根节点。然后，依次扫描$S$中的每个字符$c$；
1. 若$p$的$c$字符指针指向一个已经存在的节点$q$，则令$p=q$
2. 若$p$的$c$字符指针指向空，则新建一个节点$q$，令$p$的$c$字符指向$q$，然后令$p=q$
当$S$中的字符扫描完毕时，在当前节点$p$上标记它是一个字符串的末尾

查找

当需要查找一个字符串$S$在字典树中是否存在时，我们令一个指针$p$起初指向根节点，然后依次扫描$S$中的每个字符$c$
1. 若$p$的$c$字符指针指向空，则说明$S$没有被插入过$Trie$，结束查找
2. 若$p$的$c$字符指针指向一个已经存在的节点$q$，则令$p=q$
若$S$中的字符扫描完毕时，若当前节点$p$被标记为一个字符串的末尾，则说明$S$在字典树中存在过，否则没有

而这道题需要找到重复出现的，所以我们再开一个$bool$数组就$ojbk$了

代码

#include<cstdio>
#include<cstring>
using namespace std;
int trie[800001][26],tot,n,m;
bool end[800001],cnt[800001];
inline void insert(char* str)//插入
{int len=strlen(str),p=1;for(register int k=0;k<len;k++){int ch=str[k]-97;if(!trie[p][ch]) trie[p][ch]=++tot;p=trie[p][ch];}end[p]=true;return;
}
inline int search(char* str)//查找
{int len=strlen(str),p=1;for(register int k=0;k<len;k++){p=trie[p][str[k]-97];if(!p) return 3;//没有找到}if(!end[p]) return 3;//没有找到if(!cnt[p]){cnt[p]++;//第一次出现return 1;}return 2;//第二题
}
signed main()
{char s[1000];scanf("%d",&n);for(register int i=1;i<=n;i++){scanf("%s",s);insert(s);}scanf("%d",&m);while(m--){scanf("%s",s);int p=search(s);if(p==1) puts("OK");if(p==2) puts("REPEAT");if(p==3) puts("WRONG");}
}