1819: [JSOI]Word Query电子字典

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.

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏xingoo, 一个梦想做发明家的程序员

Sqoop切分数据的思想概况

Sqoop通过--split-by指定切分的字段,--m设置mapper的数量。通过这两个参数分解生成m个where子句,进行分段查询。因此sqoop的spl...

19950
来自专栏计算机视觉与深度学习基础

Leetcode 65 Valid Number DFA有限状态机

Validate if a given string is numeric. Some examples: "0" => true " 0.1 " =>...

25860
来自专栏李蔚蓬的专栏

第10-11周Python学习周记

3.时间允许的话,尽可能了解一些身为程序员必要掌握的知识(例如json,参考于网络资源)。

14210
来自专栏yw的数据分析

data.table包使用应该注意的一些细节

  注意默认nThread=getDTthreads(),即使用所有能用的核心,但并不是核心用的越多越好,本人亲自测试的情况下,其实单核具有较强的性能,只有在数...

8310
来自专栏漏斗社区

HASH函数烧脑大作战

本期讲解一下hash函数,由于之前在比赛中做到了一题hash有关的题目,引发了此次的深(烧)度(脑)研究,本来想讲讲原理,但是太难,看得很痛苦,所以此次通过结合...

14250
来自专栏*坤的Blog

hdu1043

17940
来自专栏腾讯技术工程官方号的专栏

后台开发中的时空转换艺术

作者介绍:augustzhang,安全平台部基础架构组员工,先后从事密保、验证码等后台研发工作,现在主要负责安全平台部大数据平台的研发工作,致力于研究每秒GB级...

22170
来自专栏云霄雨霁

数据结构----符号表

19600
来自专栏申龙斌的程序人生

零基础学编程018:条件语句

学习了《零基础学编程017:画出我的公众号LOGO》之后,可以用几行代码,画出一个螺旋渐开线。 from turtle import * for i in r...

35860
来自专栏技术博文

php pathinfo()的用法

pathinfo — 返回文件路径的信息  mixed pathinfo ( string $path [, int $options = PATHINFO_D...

41770

扫码关注云+社区

领取腾讯云代金券