求助,字典树wa了最后一个点
查看原帖
求助,字典树wa了最后一个点
579489
Vigilant_Yaksha楼主2023/5/20 17:28
#include<bits/stdc++.h>
#define maxn 500100
using namespace std;
typedef unsigned long long ull;
int t,n,m;
string c;
int cnt=1;
struct node{
	int son[90];
	int ans;
}tree[maxn];
bool l[maxn][210];
int p=0;
int f(char y) {
	if(y>='A'&&y<='Z')return y-'A';
	else if(y>='a'&&y<='z')return y-'a'+26;
	else if(y>='0'&&y<='9')return y-'0'+52;
}
void add(string x) {
	int now=0;
	for(int i=0; i<=x.size(); i++) {
		int to=f(x[i]);
		if(tree[now].son[to]==0) {
			tree[now].son[to]=++cnt;
		}
		now=tree[now].son[to];
	}
	l[now][p]=true;
}
void joker(string x){
	int now=0;
	bool ou=true;
	for(int i=0; i<=x.size(); i++) {
		int to=f(x[i]);
		if(tree[now].son[to]==0) {
			ou=false;
			break;
		}
		now=tree[now].son[to];
	}
	if(ou)
	for(int i=1;i<=t;i++){
		if(l[now][i]==true){
			cout<<i<<" ";
		}
	}
	cout<<"\n";
}
int main() {
	cin>>t;
	for(p=1;p<=t;p++){
		cin>>n;
		for(int i=1; i<=n; i++) {
			cin>>c;
			add(c);
		}	
	}
	cin>>m;
	for(int i=1; i<=m; i++) {
		cin>>c;
		joker(c);
	}
	return 0;
}
//不开 long long 见祖宗
//不取模模 见祖宗
2023/5/20 17:28
加载中...