1819: [JSOI]Word Query电子字典

浏览数：27 / 时间：2015年06月09日

1819: [JSOI]Word Query电子字典

Time Limit: 10 Sec Memory Limit: 64 MB
Submit: 729 Solved: 238
[Submit][Status]

Description

人们在英文字典中查找某个单词的时候可能不知道该单词的完整拼法，而只知道该单词的一个错误的近似拼法，这时人们可能陷入困境，为了查找一个单词而浪费大量的时间。带有模糊查询功能的电子字典能够从一定程度上解决这一问题：用户只要输入一个字符串，电子字典就返回与该单词编辑距离最小的几个单词供用户选择。字符串a与字符串b的编辑距离是指：允许对a或b串进行下列“编辑”操作，将a变为b或b变为a，最少“编辑”次数即为距离。 ? 删除串中某个位置的字母； ? 添加一个字母到串中某个位置； ? 替换串中某一位置的一个字母为另一个字母； JSOI团队正在开发一款电子字典，你需要帮助团队实现一个用于模糊查询功能的计数部件：对于一个待查询字符串，如果它是单词，则返回-1；如果它不是单词，则返回字典中有多少个单词与它的编辑距离为1。

Input

第一行包含两个正整数N (N < = 10,000)和M (M < = 10,000)。接下来的N行，每行一个字符串，第i + 1行为单词Wi。单词长度在1至20之间。再接下来M行，每行一个字符串，第i + N + 1表示一个待查字符串Qi。待查字符串长度在1至20之间。Wi和Qi均由小写字母构成，文件中不包含多余空格。所有单词互不相同，但是查询字符串可能有重复。提示：有50%的数据范围：N < = 1,000，M < = 1,000。

Output

输出应包括M行，第i行为一个整数Xi。Xi = -1表示Qi为字典中的单词；否则Xi表示与Qi编辑距离为1的单词的个数。

Sample Input

4 3
abcd
abcde
aabc
abced
abcd
abc
abcdd

Sample Output

-1
2
3

HINT

abcd在单词表中出现过；abc与单词abcd、aabc的编辑距离都是1；abcdd与单词abcd、abcde、abced的编辑距离都是1。

Source

JSOI第二轮Contest1

题解：这道题目里面的编辑距离为1，也就是三种最基本的情况，而且对于字典树而言都不难操作，所以直接乱搞搞就是啦（只要你会字典树）

  1 /**************************************************************
  2     Problem: 1819
  3     User: HansBug
  4     Language: Pascal
  5     Result: Accepted
  6     Time:856 ms
  7     Memory:22080 kb
  8 ****************************************************************/
  9  
 10 type
 11     point=^node;
 12     node=record
 13                ex:longint;
 14                next:array[‘A‘..‘Z‘] of point;
 15                chi,bro:point;
 16                ct:char;
 17     end;
 18 var
 19    i,j,k,l,m,n,TP:longint;
 20    head,p,p1:point;
 21    s1:ansistring;
 22 function getpoint:point;inline;
 23          var p:point;c1:char;
 24          begin
 25               new(p);
 26               p^.ex:=0;p^.chi:=nil;
 27               p^.bro:=nil;
 28               for c1:=‘A‘ to ‘Z‘ do p^.next[c1]:=nil;
 29               exit(p);
 30          end;
 31 procedure add(p:point;c1:char);inline;
 32           begin
 33                if p^.next[c1]<>nil then exit;
 34                p^.next[c1]:=getpoint;
 35                p^.next[c1]^.ct:=c1;
 36                p^.next[c1]^.bro:=p^.chi;
 37                p^.chi:=p^.next[c1];
 38           end;
 39 procedure add(s1:ansistring);
 40           var
 41              p:point;i:longint;
 42           begin
 43                p:=head;
 44                for i:=1 to length(s1) do
 45                    begin
 46                         add(p,s1[i]);
 47                         p:=p^.next[s1[i]];
 48                    end;
 49                p^.ex:=1;
 50           end;
 51 function exist(head:point;s1:ansistring;x:longint):boolean;inline;
 52          var p:point;i:longint;
 53          begin
 54               p:=head;
 55               for i:=1 to length(s1) do
 56                   begin
 57                        if p^.next[s1[i]]=nil then exit(false);
 58                        p:=p^.next[s1[i]];
 59                   end;
 60               if x=0 then exit(not(p^.ex=0));
 61               if (p^.ex>0) and (p^.ex<>tp) then
 62                  begin
 63                       p^.ex:=tp;
 64                       exit(true)
 65                  end
 66               else exit(false);
 67          end;
 68 function more(s1:ansistring):longint;
 69          var
 70             p:point;i,j,k,l:longint;
 71          begin
 72               inc(tp);
 73               p:=head;l:=0;
 74               for i:=1 to length(s1) do
 75                   begin
 76                        if exist(p,copy(s1,i+1,length(s1)-i),1) then inc(l);
 77                        if p^.next[s1[i]]=nil then exit(l);
 78                        p:=p^.next[s1[i]];
 79                   end;
 80               exit(l);
 81          end;
 82 function just(s1:ansistring):longint;
 83          var p,P1:point;i,j,k,l:longint;
 84          begin
 85               inc(tp);
 86               p:=head;l:=0;
 87               for i:=1 to length(s1)-1 do
 88                   begin
 89                        p1:=p^.chi;
 90                        while p1<>nil do
 91                              begin
 92                                   if exist(p1,copy(s1,i+1,length(s1)-i),1) then inc(l);
 93                                   p1:=p1^.bro;
 94                              end;
 95                        if p^.next[s1[i]]=nil then exit(l);
 96                        p:=p^.next[s1[i]];
 97                   end;
 98               if p^.chi=nil then exit(l);
 99               p1:=p^.chi;
100               while p1<>nil do
101                     begin
102                          if (p1^.ex>0) and (p1^.ex<>tp) then inc(l);
103                          p1:=p1^.bro;
104                     end;
105               exit(l);
106          end;
107 function less(s1:ansistring):longint;
108          var p,p1:point;i,j,k,l:longint;
109          begin
110               inc(tp);
111               p:=head;l:=0;
112               for i:=1 to length(s1) do
113                   begin
114                        p1:=p^.chi;
115                        while p1<>nil do
116                              begin
117                                   if exist(p1,copy(s1,i,length(s1)-i+1),1) then inc(l);
118                                   p1:=p1^.bro;
119                              end;
120                        if p^.next[s1[i]]=nil then exit(l);
121                        p:=p^.next[s1[i]];
122                   end;
123               p1:=p^.chi;
124               while p1<>nil do
125                     begin
126                          if (p1^.ex>0) and (p1^.ex<>tp) then inc(l);
127                          p1:=p1^.bro;
128                     end;
129               exit(l);
130          end;
131 begin
132      
133      readln(n,m);
134      head:=getpoint;
135      for i:=1 to n do
136          begin
137               readln(s1);
138               add(upcase(s1));
139          end;
140      tp:=2;
141      for i:=1 to m do
142          begin
143               readln(s1);
144               s1:=upcase(s1);
145               if exist(head,s1,0) then
146                  begin
147                       writeln(-1);
148                       continue;
149                  end;
150               writeln(more(s1)+just(s1)+less(s1));
151          end;
152  
153 end.