自动搬运

查看原文

来自洛谷，原作者为

	Utsuji_risshū **

搬运于2025-08-24 21:59:51，当前版本为作者最后更新于2018-07-07 18:15:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

这道题用Trie树做的话，建好树之后对于每一个查询单词，其实就是暴力枚举出其添加1个字母、替换1个字母或者删去1个字母后的字符串在不在树上。具体枚举的话可以循环模拟但我太弱了写不出来，有点繁。这里我用的是DFS，相当于是在Trie树上做3种查找，等效于3种编辑方式。我们用DFS(root,length,f)表示目前在查root节点的孩子中是否有s[length]这一位的字符，f表示“编辑”机会是否用过。

1.删除：相当于忽略当前字符在树上的存在，直接跳到下一个字符继续找，即进行DFS(root,length+1,1)；

2.添加：相当于在root孩子中继续查剩下s[length]~s[size-1]的串，即进行DFS(Trie[root][i],length,1),这里是要枚举26种情况的;

3.替换：相当于在root孩子中继续查剩下s[length+1]~s[size-1]的串，即进行DFS(Trie[root][i],length+1,1),这里也要枚举26种情况，并且替换字母不能和后一位字符相同；

此外，除以上3种查询方式，还有最基本的Trie树查询，即字符串不经过修改是否存在。然后就没什么问题了，注意防止不同的修改出现相同串即可。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=10000+7;
int Trie[MAXN*20][26],visx[MAXN];//visx[i]存足修改要求后的字符串末节点 
char s[22];
bool p[MAXN*20],vis[MAXN*20],word;//p表示p[rt]是否是单词节点，vis[rt]表示rt是否已经是满足修改要求后的字符串 
int n,m,u,len,tot,vistot;

void Insert(){
	u=0,len=strlen(s);
	for(register int i=0;i<len;++i){
		int c=s[i]-'a';
		if(!Trie[u][c]) Trie[u][c]=++tot;
		u=Trie[u][c];
	}
	p[u]=1;
}

void DFS(int rt,int l,bool f){
	if(l==len&&p[rt]&&!f){
		word=1;return;
	}//Trie树本来就存在的 
	if(l==len&&p[rt]&&f){
		if(!vis[rt]) vis[visx[++vistot]=rt]=1;
		return;
	}//经过修改而存在的标记下来，那句赋值没看懂的话就是vis标记一下，同时往visx里装 
	int c=s[l]-'a';
	if(!f){
		if(l<len) DFS(rt,l+1,1);//l=len无意义 
		for(register int i=0;i<26;++i)
			if(Trie[rt][i]){
				DFS(Trie[rt][i],l,1);
				if(i!=c) DFS(Trie[rt][i],l+1,1);
			}//添加和替换可以合起来 
	}
	if(l>=len) return;//长度到了但没单词，返回。注意到len长度是也是可以添加的。 
	if(Trie[rt][c]) DFS(Trie[rt][c],l+1,f);//直接查 
}

int main(){
	scanf("%d%d",&n,&m);
	for(register int i=1;i<=n;++i) scanf("%s",s),Insert();
	for(register int i=1;i<=m;++i){
		scanf("%s",s);len=strlen(s);
		DFS(0,0,0);
		if(word) printf("-1\n");
		else printf("%d\n",vistot);
		while(vistot) vis[visx[vistot--]]=0;//把记录都倒掉 
		word=0;
	}
}

感谢JimmyL发现的一处错误