1819: [JSOI]Word Query电子字典
1819: [JSOI]Word Query电子字典
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 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.