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;
}