字典树模板题RE,30分求助
  • 板块学术版
  • 楼主南瓜桐
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/10/24 20:27
  • 上次更新2024/10/24 21:12:21
查看原帖
字典树模板题RE,30分求助
439327
南瓜桐楼主2024/10/24 20:27

rt, orz
P2580 于是他错误的点名开始了

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int maxn = 1e4 + 1;
struct trie{
	int nxt[maxn * 50][30], cnt = 0;
	int exist[maxn];
	trie(){
		memset (exist, 0, sizeof(exist));
	}
	void insert(char *s, int l){
		int p = 0;
		for(int i = 0; i < l; ++i){
			int c = s[i] - 'a';
			if(!nxt[p][c]) nxt[p][c] = ++cnt;
			p = nxt[p][c];
		}
		++exist[p];
	}
	
	int find(char *s, int l){
		int p = 0;
		for(int i = 0; i < l; ++i){
			int c = s[i] - 'a';
			if(!nxt[p][c]) return 0;
			p = nxt[p][c];
		}
		return exist[p];
	}
}tr;
int main(){
//	freopen("P2580_5.in", "r", stdin);
	cin >> n;
	char s[51] = {};
	for(int i = 1; i <= n; ++i){
		scanf("%s", s);
		tr.insert(s, strlen(s));
	}
	cin >> m;
	do{
		scanf("%s", s);
		int t = tr.find(s, strlen(s));
		if(t == 0) printf("%s\n", "WRONG");
		else if(t == 1) printf("%s\n", "OK"), tr.insert(s, strlen(s));
		else printf("%s\n", "REPEAT");
	}while(--m);
	return 0;
}
2024/10/24 20:27
加载中...