字典树代码tle的疑问
查看原帖
字典树代码tle的疑问
1168470
prolu楼主2024/4/17 13:48
#include<bits/stdc++.h>
using namespace std;
char ss[2500];
int ott=0,id;
int tied[3000000][80],sum[3000000];

void insert(){
	int root=0;
	int len=strlen(ss);
	for(int i=0;i<len;i++){
		id=ss[i]-'0';
		if(tied[root][id]==0){
			ott++;
			tied[root][id]=ott;
		} 
		root=tied[root][id];
		sum[root]++;//此时的root 表示父节点的标号 sum则表示被访问的次数
	}
}

int search(){
	int root=0;
	int len=strlen(ss);
	for(int i=0;i<len;i++){
		int id=ss[i]-'0';
		if(tied[root][id]==0)return 0;
		root=tied[root][id];//更新
	}
	return sum[root];
	
}

int main(){
	int n,m,z;
	cin>>n;
	while(n--){
		memset(sum,0,sizeof(sum));
		memset(tied,0,sizeof(tied));
		cin>>m>>z;//m是给的字符典  z是询问的次数
		ott=0;
		while(m--){
			cin>>ss;
			insert();
		}//获取并建立我们的字典树;
		int ans=0;
		while(z--){
			cin>>ss;
			ans=search();
			cout<<ans<<endl;
		}
	}
	return 0;
}
## ```有没有大佬帮忙看看我这个代码为什么会出现wa和tle的问题,回复闭关,谢谢啦谢谢啦。
2024/4/17 13:48
加载中...