字典树 52 分求助
查看原帖
字典树 52 分求助
449457
IYSY2009I楼主2022/11/11 21:40

RT,另外问一下我这种 700700 多 MB 的写法真的有用吗

#include<iostream>
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
int read(){
	int x=0,f=1;
	char c=getchar();
	while(c<'0'||c>'9'){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=(x<<1)+(x<<3)+c-'0';
		c=getchar();
	}
	return x*f;
}
struct tree{
	int son[62];
	int str=0;
};
tree tr[3000005];
char s[3000005];
char abcd;
void cf(){
	int cnt=0;
	int n=read(),q=read();
	for(int i=1;i<=n;i++){
		cin>>s;
		int ls=strlen(s);
		int id=0;
		for(int i=0;i<ls;i++){
			int tmp=(s[i]>='a'&&s[i]<='z')?s[i]-'a':((s[i]>='A'&&s[i]<='Z')?s[i]-'A'+26:s[i]-'0'+52);
			if(tr[id].son[tmp]){
				id=tr[id].son[tmp];
				tr[id].str++;
			}
			else{
				cnt++;
				tr[cnt].str=1;
				tr[id].son[tmp]=cnt;
				id=cnt;
			}
		}
	}
	for(int i=1;i<=q;i++){
		cin>>s;
		int ls=strlen(s);
		int id=0;
		bool flag=1;
		for(int i=0;i<ls;i++){
			int tmp=(s[i]>='a'&&s[i]<='z')?s[i]-'a':((s[i]>='A'&&s[i]<='Z')?s[i]-'A'+26:s[i]-'0'+52);
			if(tr[id].son[tmp]) id=tr[id].son[tmp];
			else{
				printf("0\n");
				flag=0;
				break;
			}
		}
		if(flag) printf("%d\n",tr[id].str);
	}
	for(int i=1;i<=cnt;i++){
		for(int j=0;j<=61;j++)
			tr[i].son[j]=0;
		tr[i].str=0;
	}
	return;
}
int main(){
    int t=read();
    for(int i=1;i<=t;i++)
    	cf();
	return 0;
}
2022/11/11 21:40
加载中...