【洛谷P2580】于是他錯誤的點名開始了【Trie樹】

題目背景

l i n k link link

XS中學化學競賽組教練是一個酷愛爐石的人。

他會一邊搓爐石一邊點名以至于有一天他連續點到了某個同學兩次，然後正好被路過的校長發現了然後就是一頓歐拉歐拉歐拉（詳情請見已結束比賽 CON900）。

題目描述

這之後校長任命你為特派探員，每天記錄他的點名。校長會提供化學競賽學生的人數和名單，而你需要告訴校長他有沒有點錯名。（為什麼不直接不讓他玩爐石。）

輸入格式

第一行一個整數 n n n，表示班上人數。

接下來 n n n 行，每行一個字元串表示其名字（互不相同，且隻含小寫字母，長度不超過 50）。

第 n + 2 n+2 n+2 行一個整數 m m m，表示教練報的名字個數。

接下來 m m m 行，每行一個字元串表示教練報的名字（隻含小寫字母，且長度不超過 50）。

輸出格式

對于每個教練報的名字，輸出一行。

如果該名字正确且是第一次出現，輸出 O K OK OK，如果該名字錯誤，輸出 W R O N G WRONG WRONG，如果該名字正确但不是第一次出現，輸出 R E P E A T REPEAT REPEAT。

輸入輸出樣例

輸入 #1

5  
a
b
c
ad
acd
3
a
a
e
           

輸出 #1

OK
REPEAT
WRONG
           

分析：

T r i e Trie Trie樹 の の の模闆題 不過它讓你看有沒有 R E P A E T REPAET REPAET

那就統計一下 每個單詞出現的次數就行了 然後看次數有沒有 重複

其他的還是一樣的 存單詞進 t r i e trie trie樹 然後 q u e r y query query 最後看看是哪種情況即可.

CODE：

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue> 
#include<bitset>
//#pragma GCC optimize(2)
#define reg register 
using namespace std;
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int N=1e5+3;
const int M=1e6+3;
struct Trie{
	int son[27],kel,cnt;
}trie[M];
int n,m,lens,tot;
char s[N];
void insert(char a[])
{
	int now=0;
	for(int i=0;i<lens;i++)
	{
		int qwq=a[i]-'a';
		if(!trie[now].son[qwq]) trie[now].son[qwq]=++tot;  //存入trie
		now=trie[now].son[qwq];
	}
	trie[now].kel++;
}
int find(char a[])
{
	int now=0,ret=0;
	for(int i=0;i<lens;i++)
	{
		int qwq=a[i]-'a';
		if(!trie[now].son[qwq]) return 0;  //沒出現的直接wrong就行了
		now=trie[now].son[qwq];
	}
	trie[now].cnt++;  //統計出現次數
	return now;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s);
		lens=strlen(s);
		insert(s);
	}
	scanf("%d",&m);
	for(int i=1;i<=m;i++)
	{
		scanf("%s",s);
		lens=strlen(s);
		int place=find(s);
		if(!trie[place].kel) puts("WRONG");
		else if(trie[place].cnt>1) puts("REPEAT");  //分情況
		else puts("OK");
	} 
	return 0;
}