这个字典树为什么是错的?
  • 板块灌水区
  • 楼主封禁用户
  • 当前回复0
  • 已保存回复0
  • 发布时间2024/12/26 18:36
  • 上次更新2024/12/26 18:45:38
查看原帖
这个字典树为什么是错的?
1533871
封禁用户楼主2024/12/26 18:36
#include<bits/stdc++.h>
using namespace std;
#define endl "\n"
int t=0;
struct node{
	int next[26];
	bool isend;
	node(){
		memset(next,-1,sizeof(next));
		isend=false;
	}
}trie[1000005];
int add(int prev,char ad,bool isend){
	if(trie[prev].next[ad-97]!=-1)return trie[prev].next[ad-97];
	trie[prev].next[ad-97]=++t;
	if(isend&&!trie[t].isend)trie[t].isend=isend;
	return t;
}
bool find(string a){
	int t=0;
	for(int i=0;i<a.size();i++){
		if(trie[t].next[a[i]-97]==-1)return false;
		t=trie[t].next[a[i]-97];
	}
	if(trie[t].isend)return true;
	return false;
}
int n,m;
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n;
	while(n--){
	string a;
	cin>>a;
	int g=0;
	for(int i=0;i<a.size();i++){
		g=add(g,a[i],i==a.size()-1?true:false);
	}
	}
	cin>>m;
	while(m--){
		string a;
		cin>>a;
		cout<<(find(a)?"Yes":"No")<<endl;
	} 
}
2024/12/26 18:36
加载中...