BZOJ1819: [JSOI]Word Query电子字典 暴力+Trie树

思路:

对于每次询问,暴力枚举所有编辑距离为1的串,然后用Trie判断存不存在并判重.

妈呀这是\(O(10000*26*20*20)=10^8\),居然也能过.

其实用Hash感觉就好多了.

有没有更好的方法?目前没想出来.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

int ch[200010][26],end[200010],vis[200010],cnt;
char s[21],ss[22];

int tclock;
inline bool judge(int len){
	int p=0;
	for(int i=0;i<len;++i){
		if(!ch[p][ss[i]-'a'])return 0;
		p=ch[p][ss[i]-'a'];
	}
	if(!end[p])return 0;
	if(vis[p]!=tclock)return vis[p]=tclock,1;else return 0;
}

int main(){
	int n,m;scanf("%d%d",&n,&m);
	register int i,j,k;
	
	int len,p,y;
	while(n--){
		scanf("%s",s);
		len=strlen(s),p=0;
		for(i=0;i<len;++i){
			y=s[i]-'a';
			if(!ch[p][y])ch[p][y]=++cnt;
			p=ch[p][y];
		}
		end[p]=1;
	}
	
	int id;
	while(m--){
		scanf("%s",s);
		len=strlen(s);
		
		p=0;
		bool find=1;
		for(i=0;i<len;++i){
			y=s[i]-'a';
			if(!ch[p][y]){find=0;break;}
			else p=ch[p][y];
		}
		if(find&&end[p]){puts("-1");continue;}
		
		int re=0;
		++tclock;
		
		if(len>1){
			for(i=0;i<len;++i){
				id=0;
				for(j=0;j<i;++j)ss[id++]=s[j];
				for(j=i+1;j<len;++j)ss[id++]=s[j];
				re+=judge(len-1);
			}
		}
		for(i=0;i<len;++i)for(j=0;j<26;++j)if(j!=s[i]-'a'){
			memcpy(ss,s,sizeof s),ss[i]='a'+j;
			re+=judge(len);
		}
		for(i=0;i<=len;++i)for(j=0;j<26;++j){
			id=0;
			for(k=0;k<i;++k)ss[id++]=s[k];
			ss[id++]='a'+j;
			for(k=i;k<len;++k)ss[id++]=s[k];
			re+=judge(len+1);
		}
		
		printf("%d\n",re);
	}
	return 0;
}