洛谷 - P2580 于是他錯誤的點名開始了(trie)

P2580 于是他錯誤的點名開始了

大緻思路

注意資料範圍，這很重要！！RE了好幾次

trie樹模闆題了，最後拿set記錄一下哪些被點過了哪些沒别點過，拿個數組存可能效率更高，偷懶了

代碼

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
#include<map>
#include<string>
#include<set>

using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f;
const int N=2e6+5;

int n, m;
int son[N][26];
int cnt[N],idx;
set<string> st;

void insert(char str[]){
	int p=0;
	for(int i=0;str[i];i++){
		int u=str[i]-'a';
		if(!son[p][u])
			son[p][u]=++idx;
		p=son[p][u];
	}
	cnt[p]++;
}

int query(char str[]){
	int p=0;
	for(int i=0;str[i];i++){
		int u=str[i]-'a';
		if(!son[p][u])
			return 0;
		p=son[p][u];
	}
	return cnt[p];
}

int main(void){
	scanf("%d",&n);
	for(int i=0;i<n;i++){
		char str[60];
		scanf("%s",str);
		insert(str);
	}
	
	scanf("%d",&m);
	for(int i=0;i<m;i++){
		char str[N];
		scanf("%s",str);
		string t(str);
		
		
		int k=query(str);
		if(k==0){
			puts("WRONG");
			continue;
		}
		if(st.count(t)){
			puts("REPEAT");
		}else{
			st.insert(t);
			puts("OK");
		}
	}

	return 0;
}

/*
 * When ability does not derserve ambition, just keep moving
 */