社区讨论

蒟蒻求调 WA1-4

P8306【模板】字典树参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo28sk1z
此快照首次捕获于
2023/10/23 09:52
2 年前
此快照最后确认于
2023/11/03 10:05
2 年前
查看原帖
CPP
#include <bits/stdc++.h>
using namespace std;

const int Kmax=3e6,MAXN=75;

int T,n,m,t,now;

string s;

struct	trieN{
	int is_l;
	int next[MAXN];
}trie[Kmax];

void fil(){
	for(int i=0;i<=t;i++){
		trie[i].is_l=0;
		for(int j=0;j<MAXN;j++){
			trie[i].next[j]=0;
		}
	} 
}

void build(int p,int i){
	trie[p].is_l++;
	now=trie[p].next[s[i]-'0'];
	if(!now) now=trie[p].next[s[i]-'0']=++t;
	if(i<s.size()-1){
		build(now,i+1);
	}
}

void find(int p,int i){
//	cout<<"   "<<p<<" "<<i<<endl;
	if(i==s.size()-1){
		cout<<trie[p].is_l<<endl;
	}else{
		now=trie[p].next[s[i]-'0'];
		if(!now) cout<<0<<endl;
		else{
			find(now,i+1);
		}
	}
}

int main(){
//	freopen("1.in","r",stdin);
//	freopen("1.out","w",stdout);
	cin>>T;
	while(T--){
		t=0;
		cin>>n>>m;
		for(int i=1;i<=n+m;i++){
			cin>>s;
			if(i<=n) build(0,0);
			else find(0,0);
		}
		fil();
	}
}

回复

1 条回复,欢迎继续交流。

正在加载回复...