站外Trie树模板RE0分求调
  • 板块学术版
  • 楼主charleshe
  • 当前回复2
  • 已保存回复2
  • 发布时间2022/8/15 10:17
  • 上次更新2023/10/27 15:22:48
查看原帖
站外Trie树模板RE0分求调
477258
charleshe楼主2022/8/15 10:17

题目大意:有 nn 个字符串,mm 次询问,每次给定一个字符串,判断该字符串是否在 nn 个字符串里出现过。

1n1041 \leq n \leq 10^41m1051 \leq m \leq 10^51s501 \leq s \leq 50,其中 ss 是每个字符串的长度。

#include <cstdio>
#include <cstring>
using namespace std;
struct Trie{
	int child[30];
	int cnt;
};
Trie T[114514];
int dot;
char c[51];
int n,m;
void insert(char s[]){
	int u=1,len=strlen(s);
	for(int i=0;i<len;i++){
		int a=s[i]-'a';
		if(T[u].child[a]==0) T[u].child[a]=++dot;
		u=T[u].child[a];
	}
	T[u].cnt++;
}
bool find(char s[]){
	int u=1,len=strlen(s);
	for(int i=0;i<len;i++){
		int a=s[i]-'a';
		if(T[u].child[a]==0) return false;
		u=T[u].child[a];
	}
	if(T[u].cnt==0) return false;
	return true;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%s",c);
		insert(c);
	}
	for(int i=1;i<=m;i++){
		scanf("%s",c);
		if(find(c)) printf("Yes\n");
		else printf("No\n");
	}
	return 0;
}
2022/8/15 10:17
加载中...