本文共 6070 字，大约阅读时间需要 20 分钟。
abcd在单词表中出现过；abc与单词abcd、aabc的编辑距离都是1；abcdd与单词abcd、abcde、abced的编辑距离都是1。
题解：这道题目里面的编辑距离为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/