BZOJ1819 [JSOI]Word Query电子字典 Trie

​​题目传送门 - BZOJ1819​​题意概括

　　字符串a与字符串b的编辑距离是指：允许对a或b串进行下列“编辑”操作，将a变为b或b变为a，最少“编辑”次数即为距离。

　　删除串中某个位置的字母；

　　添加一个字母到串中某个位置；

　　替换串中某一位置的一个字母为另一个字母；

　　对于一个待查询字符串，如果它是单词，则返回-1；如果它不是单词，则返回字典中有多少个单词与它的编辑距离为1。

题解

　　根据输入的单词构建trie，然后大力搜索即可。

　　dfs，时间复杂度为m*20*20*20可以过去

代码

#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cmath>
using namespace std;
const int N=10005,L=20+5;
struct Trie{
  int e,Next[26];
  void init(){
    e=0;
    memset(Next,0,sizeof Next);
  }
}tree[N*L];
int n,m,ans,trie_cnt,len,addv[N],mark;
char ch[L];
void build(char ch[],int bh){
  int rt=1,t,len=strlen(ch);
  for (int i=0;i<len;i++){
    t=ch[i]-'a';
    if (!tree[rt].Next[t])
      tree[tree[rt].Next[t]=++trie_cnt].init();
    rt=tree[rt].Next[t];
  }
  tree[rt].e=bh;
}
void init_trie(){
  tree[1].init();
  trie_cnt=1;
}
bool dfs(int pos,int rt,bool used){
  if (pos>=len){
    if (!used)
      for (int i=0;i<26;i++)
        if (tree[rt].Next[i])
          if (dfs(pos,tree[rt].Next[i],1))
            return 1;
    if (tree[rt].e==0)
      return 0;
    if (!used)
      return 1;
    if (addv[tree[rt].e]!=mark)
      ans++;
    addv[tree[rt].e]=mark;
    return 0;
  }
  int t=ch[pos]-'a';
  if (used){
    if (!tree[rt].Next[t])
      return 0;
    return dfs(pos+1,tree[rt].Next[t],1);
  }
  //not used
  if (tree[rt].Next[t])
    if (dfs(pos+1,tree[rt].Next[t],0))
      return 1;
  //add & change 
  for (int i=0;i<26;i++)
    if (tree[rt].Next[i]){
      int nxt=tree[rt].Next[i];
      if (dfs(pos,nxt,1))
        return 1;
      if (t!=i)
        if (dfs(pos+1,nxt,1))
          return 1;
    }
  // delete
  if (dfs(pos+1,rt,1))
    return 1;
  return 0;
}
int main(){
  scanf("%d%d",&n,&m);
  init_trie();
  for (int i=1;i<=n;i++){
    scanf("%s",ch);
    build(ch,i);
  }
  memset(addv,0,sizeof addv);
  for (int i=1;i<=m;i++){
    mark=i;
    scanf("%s",ch);
    len=strlen(ch);
    ans=0;
    if (dfs(0,1,0)){
      puts("-1");
      continue;
    }
    printf("%d\n",ans);
  }
  return 0;
}