博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
1819: [JSOI]Word Query电子字典
阅读量:403 次
发布时间:2019-03-05

本文共 6070 字,大约阅读时间需要 20 分钟。

1819: [JSOI]Word Query电子字典

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

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

 

题解:这道题目里面的编辑距离为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 do101                     begin102                          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          begin110               inc(tp);111               p:=head;l:=0;112               for i:=1 to length(s1) do113                   begin114                        p1:=p^.chi;115                        while p1<>nil do116                              begin117                                   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 do125                     begin126                          if (p1^.ex>0) and (p1^.ex<>tp) then inc(l);127                          p1:=p1^.bro;128                     end;129               exit(l);130          end;131 begin132      133      readln(n,m);134      head:=getpoint;135      for i:=1 to n do136          begin137               readln(s1);138               add(upcase(s1));139          end;140      tp:=2;141      for i:=1 to m do142          begin143               readln(s1);144               s1:=upcase(s1);145               if exist(head,s1,0) then146                  begin147                       writeln(-1);148                       continue;149                  end;150               writeln(more(s1)+just(s1)+less(s1));151          end;152  153 end.

 

转载地址:http://xdezz.baihongyu.com/

你可能感兴趣的文章