题解 P4407 【[JSOI2009]电子字典】

· · 题解

这道题用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发现的一处错误