Bless You Autocorrect!

题目链接：

https://odzkskevi.qnssl.com/0c87453efec2747f8e8a573525fd42f9?v=1533651456

题解：

这是一道Trie+BFS的题目；这是第二次写了 Orz 还是WA好几发；

这一题，我们可以用字典树存已有的单词，在存的时候，记录一下该节点所能到达的最深的位置，并且记录它的父亲节点；

然后BFS跑一遍，对于每一步只有3种走法，走这一个字母，删除该位置的父亲字母，跳到它所能到达的最深位置；然后者

每一步都是在上一个字母的基础上步数加一的；

  1 #include<iostream>
  2 #include<cstdio>
  3 #include<cstring>
  4 #include<string>
  5 #include<queue>
  6 #include<cmath>
  7 #include<map>
  8 #include<algorithm>
  9 using namespace std;
 10 typedef long long LL;
 11 const int INF=0x3f3f3f3f;
 12 const LL inf=0x3f3f3f3f3f3f3f3fLL;
 13 const int maxn=2e6+5;
 14 const int sigma_size=26;
 15 char s[maxn];
 16 
 17 struct Trie{
 18     int ch[maxn][sigma_size];
 19     int flag[maxn],fa[maxn],dep[maxn],vis[maxn];
 20     int pos,root;
 21 
 22     int Idx(char ch) { return ch-'a'; }
 23     
 24     void Init()
 25     {
 26         pos=1;root=0;
 27         memset(ch,0,sizeof ch);
 28         memset(dep,0,sizeof dep);
 29         memset(vis,0,sizeof vis);
 30         memset(flag,-1,sizeof flag);
 31         memset(fa,-1,sizeof fa);
 32     }
 33     
 34     void Insert(char *s)
 35     {
 36         int u=0,n=strlen(s);
 37         for(int i=0;i<n;i++)
 38         {
 39             int c=Idx(s[i]);
 40             if(!ch[u][c])
 41             {
 42                 ch[u][c]=pos++;
 43                 fa[ch[u][c]]=u;
 44             }
 45             u=ch[u][c];
 46         }
 47         int end=u;
 48         u=0;
 49         for(int i=0;i<n;i++) 
 50         {
 51             int c=Idx(s[i]);
 52             u=ch[u][c];
 53             if(flag[u]==-1) flag[u]=end;
 54         }
 55     }
 56     
 57     void Search()
 58     {
 59         queue<int> q;
 60         q.push(root); vis[root]=1; dep[root]=0;
 61         while(!q.empty())
 62         {
 63             int u=q.front(); q.pop();
 64             
 65             for(int i=0;i<26;i++)
 66             {
 67                 if(!ch[u][i] || vis[ch[u][i]]) continue;
 68                 vis[ch[u][i]]=1;
 69                 dep[ch[u][i]]=dep[u]+1;
 70                 q.push(ch[u][i]);
 71             }
 72             
 73             int v=fa[u];
 74             if(v!=-1 && !vis[v])
 75             {
 76                 vis[v]=1;
 77                 dep[v]=dep[u]+1;
 78                 q.push(v);
 79             }
 80             
 81             v=flag[u];
 82             if(v!=-1 && !vis[v])
 83             {
 84                 vis[v]=1;
 85                 dep[v]=dep[u]+1;
 86                 q.push(v);
 87             }    
 88         }    
 89     }
 90     
 91     int Query(char *s)
 92     {
 93         int u=0,i;
 94         for(i=0;i<strlen(s);i++)
 95         {
 96             if(!ch[u][Idx(s[i])]) break;
 97             u=ch[u][Idx(s[i])];
 98         }
 99         return dep[u]+strlen(s)-i; //没有的还要一个一个打上去 
100     }
101         
102 } Tree;
103 
104 int main()
105 {
106     int n,m;
107     while(scanf("%d%d",&n,&m)!=EOF)
108     {
109         Tree.Init();
110         for(int i=1;i<=n;i++)
111         {
112             scanf("%s",s);
113             Tree.Insert(s);
114         }
115         Tree.Search();
116         for(int i=1;i<=m;i++)
117         {
118             scanf("%s",s);
119             cout<<Tree.Query(s)<<endl;
120         }
121     }
122     return 0;
123 }

View Code